Obstructions for three-coloring graphs without induced paths on six vertices

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We prove that there are 24 4-critical P6-free graphs, and give the complete list. We remark that, if H is connected and not a subgraph of P6, there are infinitely many 4-critical H-free graphs. Our result answers questions of Golovach et al. and Seymour.

Original languageEnglish (US)
Pages (from-to)45-83
Number of pages39
JournalJournal of Combinatorial Theory. Series B
Volume140
DOIs
StatePublished - Jan 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Critical graph
  • Forbidden induced paths
  • Graph coloring

Fingerprint Dive into the research topics of 'Obstructions for three-coloring graphs without induced paths on six vertices'. Together they form a unique fingerprint.

Cite this