Discrete & Computational Math Seminar (DisCoMath)
On the hardness of (P3, H)-Non-Arrowing
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.
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
When and Where
This is an RIT Only Event