Discrete & Computational Math Seminar: Zohair Hassan
Discrete & Computational Math Seminar (DisCoMath)
On the hardness of (P3, H)-Non-Arrowing
Zohair Hassan
GCCIS, RIT
Zoom Registration Link
Abstract:
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
Event Snapshot
When and Where
Who
This is an RIT Only Event
Interpreter Requested?
No