Browsing Waterloo Research by Author "Trotignon, Nicolas"
Now showing items 1-1 of 1
-
Triangle-free graphs that do not contain an induced subdivision of K4 are 3-colorable
Chudnovsky, Maria; Liu, Chun-Hung; Schaudt, Oliver; Spirkl, Sophie; Trotignon, Nicolas; Vušković, Kristina (Wiley, 2019-10)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ć.