Obstructions for three-coloring and list three-coloring h -free graphs

Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, Mingxian Zhong

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability.

Original languageEnglish (US)
Pages (from-to)431-469
Number of pages39
JournalSIAM Journal on Discrete Mathematics
Volume34
Issue number1
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Critical graph
  • Graph coloring
  • Induced subgraph

Fingerprint Dive into the research topics of 'Obstructions for three-coloring and list three-coloring h -free graphs'. Together they form a unique fingerprint.

Cite this