Triangle‐free graphs that do not contain an induced subdivision of K 4 are 3‐colorable

Maria Chudnovsky (1) , Chun‐hung Liu , Oliver Schaudt (2) , Sophie Spirkl (3) , Nicolas Trotignon (4, 5, 6) , Kristina Vušković (7)

1 Columbia University [New York]
2 C&O - Equipe combinatoire et optimisation
3 Princeton University
4 LIP - Laboratoire de l'Informatique du Parallélisme
5 CNRS - Centre National de la Recherche Scientifique
6 MC2 - Modèles de calcul, Complexité, Combinatoire
7 School of Computing [Leeds]

We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of K 4 are 3-colorable. This proves a conjecture of Trotignon and Vušković [5].

Domaines: Mathématique discrète [cs.DM]

Maria Chudnovsky, Chun‐hung Liu, Oliver Schaudt, Sophie Spirkl, Nicolas Trotignon, et al.. Triangle‐free graphs that do not contain an induced subdivision of K 4 are 3‐colorable. Journal of Graph Theory, 2018. ⟨hal-01993783⟩