Discrete & Computational Math Seminar: Zohair Hassan

Event Image
Discrete & Computational Math Seminar (DisCoMath)

Discrete & Computational Math Seminar (DisCoMath)
On the hardness of (P3, H)-Non-Arrowing
Zohair Hassan

Zoom Registration Link


Graph arrowing is concerned with determining which monochromatic subgraphs are unavoidable when coloring a given graph. The complexity of various arrowing problems has been studied for decades, particularly when the subgraphs to be avoided are fixed. Some cases have been shown to be solvable in polynomial time or NP-complete. We focus on the latter case. In this presentation, we will focus on (P3, H)-Non-Arrowing; determining whether it is possible to color a given graph's edges red or blue such that there are no red P3's or blue H's, where P3 is the path graph on three vertices, and H is a fixed graph. In particular, we will observe how structural properties (e.g., k-connectivity) of H allow us to construct gadgets to reduce a variant of SAT to the (P3, H)-Non-Arrowing problem. This provides hardness results for an infinitely large family of H.

Intended Audience:
Undergraduates, graduates, and experts. Those with interest in the topic.

Keep up with DisCoMath Seminars on the DisCoMathS webpage.

To request an interpreter, please visit myaccess.rit.edu

Brendan Rooney
Event Snapshot
When and Where
February 28, 2023
3:30 pm - 4:30 pm
Room/Location: 2154

This is an RIT Only Event

Interpreter Requested?


student experience