The 3-colorability conjecture for triangle- and ISK4-free graphs
The 3-colorability conjecture for triangle- and ISK4-free graphs
Here graphs are simple and finite. A graph is triangle-free if it contains no triangle and ISK4-free if it contains no induced subdivision of , where is the complete graph on four vertices. A graph is 3-colorable if its vertices can be colored with three colors so that adjacent vertices receive different colors. The 3-colorability conjecture for triangle- and ISK4-free graphs. Every triangle-free, ISK4-free graph is 3-colorable. The paper states that this conjecture follows from the preceding low-degree vertex conjecture and proves both conjectures for graphs of girth at least ; the unrestricted case remains open in the supplied text.
Sources & referencesView supporting material
Primary source
Nicolas Trotignon and Kristina Vušković, “On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph”, arXiv:1407.6531 (2014).
Additional references
2 papers in this index state this conjecture (2013–2014). The statement above is taken from the most recent of them; the others are arXiv:1308.6678.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.