Obstructions for three-coloring graphs with one forbidden induced subgraph

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages1774-1783
Number of pages10
ISBN (Electronic)9781510819672
DOIs
StatePublished - Jan 1 2016
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume3

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Obstructions for three-coloring graphs with one forbidden induced subgraph'. Together they form a unique fingerprint.

Cite this