Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable

Maria Chudnovsky, Chun Hung Liu, Oliver Schaudt, Sophie Spirkl, Nicolas Trotignon, Kristina Vušković

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3-colorable. This proves a conjecture of Trotignon and Vušković [J. Graph Theory. 84 (2017), no. 3, pp. 233–248].

Original languageEnglish (US)
Pages (from-to)67-95
Number of pages29
JournalJournal of Graph Theory
Volume92
Issue number2
DOIs
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • coloring
  • induced subgraph

Fingerprint Dive into the research topics of 'Triangle-free graphs that do not contain an induced subdivision of K<sub>4</sub> are 3-colorable'. Together they form a unique fingerprint.

Cite this