DisCoMath Seminar: On the Hardness of Graph Arrowing Part 1
Discrete & Computational Math Seminar (DisCoMath)
On the Hardness of Graph Arrowing: A Combinatorial Computing Approach Part 1
Zohair Hassan
Register Here for Zoom Link
This seminar may be attended in person in 3305 Gosnell Hall or online via Zoom.
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 to be coNP-complete. We focus on the latter case. Previous hardness proofs typically rely on ad-hoc, laborious constructions of "gadgets." We propose searching for gadgets computationally. These gadgets will allow us to simulate variants of SAT, thus showing coNP-hardness.
In this presentation, we will focus on P3P5-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 P5's, where Pn is the path graph on n vertices. We will show that P3P5-Arrowing is coNP-complete by discussing the properties of gadgets that may be used in a proof.
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
Open to the Public
Interpreter Requested?
No