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 K4K_4, where K4K_4 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 55; 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.