← All problems

Lévêque–Maffray–Trotignon ISK4-free graph colouring conjecture

For every finite graph GG, if GG contains no induced subgraph isomorphic to a subdivision of K4K_4, then χ(G)≤4\chi(G)\le 4.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new, unverified result proves the four-colour bound for diamond-free graphs, but the original conjecture for all graphs remains open.

Lévêque, Maffray, and Trotignon conjectured in 2012 that every ISK4-free graph is 44-colorable.

Known results

  • {ISK4,wheel0˘07f}\{\mathrm{ISK4},\text{wheel}\u007f\}-free graphs are 33-colorable (Lévêque, Maffray, Trotignon).
  • χ(G)≤40˘07f\chi(G)\le 4\u007f for {ISK4,triangle0˘07f}\{\mathrm{ISK4},\text{triangle}\u007f\}-free graphs, and χ(G)≤240˘07f\chi(G)\le 24\u007f for all ISK4-free graphs (2016).
  • Triangle-free ISK4-free graphs are 33-colorable (published 2019).
  • ISK4-free graphs containing a K1,2,3K_{1,2,3} are 44-colorable (2023).

October 23, 2026 restricted theorem

Qing Cui and Kaiyang Lan report that every diamond-free graph containing no subdivision of K4K_4 has chromatic number at most 44, with optimality in that subclass. This is a restricted advance, not a solution of the full conjecture, and the result is not independently verified here.

Current status (as of October 2026): The four-colour bound is claimed for the diamond-free subclass, while the full ISK4-free conjecture remains open.

Sources

Solutions 0

No solutions have been posted yet.