Description
The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory. An especially intriguing case is that of 3-colorability. Here, the state of the art is our recent poly-time algorithm to solve the problem on graphs without induced paths on seven vertices, so-called P_7-free graphs.
So far, much less was known about certification in this context. We prove that there are 24 minimally non-3-colorable graphs in the class of P_6-free graphs, and give the complete list. In particular, we obtain a certifying algorithm for 3-coloring graphs in this class, which was an open problem posed by Golovach et al.
We also show that our result is best possible, in the following sense. If H is a connected graph that is not a subgraph of P_6, then there are infinitely many minimally non-3-colorable H-free graphs.
Joint work with Flavia Bonomo, Maria Chudnovsky, Peter Maceli, Maya Stein, and Mingxian Zhong resp. Maria Chudnovsky, Jan Goedgebeur, and Mingxian Zhong.
Primary author
Dr
Oliver Schaudt
(University of Cologne)
