K4-free graphs with no odd holes

Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas

Research output: Contribution to journalArticle

17 Scopus citations

Abstract

All K4-free graphs with no odd hole and no odd antihole are three-colourable, but what about K4-free graphs with no odd hole? They are not necessarily three-colourable, but we prove a conjecture of Ding that they are all four-colourable. This is a consequence of a decomposition theorem for such graphs; we prove that every such graph either has no odd antihole, or belongs to one of two explicitly-constructed classes, or admits a decomposition.

Original languageEnglish (US)
Pages (from-to)313-331
Number of pages19
JournalJournal of Combinatorial Theory. Series B
Volume100
Issue number3
DOIs
StatePublished - May 1 2010

All Science Journal Classification (ASJC) codes

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

Keywords

  • Odd hole
  • Perfect graph

Fingerprint Dive into the research topics of 'K<sub>4</sub>-free graphs with no odd holes'. Together they form a unique fingerprint.

  • Cite this