Triangle-free graphs that do not contain an induced subdivision of are 3-colorable
arXiv:1704.08104 · doi:10.1002/jgt.22441
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 Vuskovic.
References in corpus (5)
- Triangle-free intersection graphs of line segments with large chromatic number
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- On graphs with no induced subdivision of
- Excluding induced subdivisions of the bull and related graphs
- On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph