TY - GEN

T1 - Obstructions for three-coloring graphs with one forbidden induced subgraph

AU - Chudnovsky, Maria

AU - Goedgebeur, Jan

AU - Schaudt, Oliver

AU - Zhong, Mingxian

PY - 2016/1/1

Y1 - 2016/1/1

N2 - The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory, an especially intruiging case being that of 3-colorability. So far, not much was known about certification in this context. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-coloring P6-free graphs, which solves an open problem posed by Golovach et al. Here, P6 denotes the induced path on six vertices.Our result leads to the following dichotomy theorem: if if is a connected graph, then there are finitely many 4-critical .H-free graphs if and only if H is a subgraph of Ps. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand.

AB - The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory, an especially intruiging case being that of 3-colorability. So far, not much was known about certification in this context. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-coloring P6-free graphs, which solves an open problem posed by Golovach et al. Here, P6 denotes the induced path on six vertices.Our result leads to the following dichotomy theorem: if if is a connected graph, then there are finitely many 4-critical .H-free graphs if and only if H is a subgraph of Ps. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand.

UR - http://www.scopus.com/inward/record.url?scp=84963543190&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963543190&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974331.ch123

DO - 10.1137/1.9781611974331.ch123

M3 - Conference contribution

AN - SCOPUS:84963543190

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1774

EP - 1783

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -