Triangle‐free graphs that do not contain an induced subdivision of K4 are 3‐colorable
Abstract
We show that triangle‐free graphs that do not contain an induced subgraph isomorphic to a subdivision of are 3‐colorable. This proves a conjecture of Trotignon and Vušković [J. Graph Theory. 84 (2017), no. 3, pp. 233–248].
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 13, 2018
- Source ID
- 10.1002/jgt.22441
Entities
People
- Chun‐Hung Liu
- Kristina Vušković
- Maria Chudnovsky
- Nicolas Trotignon
- Oliver Schaudt
- Sophie Spirkl
Organizations
- Agence Nationale de la Recherche
- Army Research Office
- Engineering and Physical Sciences Research Council
- National Science Foundation Division of Mathematical Sciences
- Princeton University
- University of Cologne
- University of Leeds
- University of Lyon