Lévêque–Maffray–Trotignon ISK4-free graph colouring conjecture
For every finite graph , if contains no induced subgraph isomorphic to a subdivision of , then .
References
- The chromatic number of {ISK4, diamond}-free graphs — arXiv — Qing Cui, Kaiyang Lan
Source: arXiv
Progress summary
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 -colorable.
Known results
- -free graphs are -colorable (Lévêque, Maffray, Trotignon).
- for -free graphs, and for all ISK4-free graphs (2016).
- Triangle-free ISK4-free graphs are -colorable (published 2019).
- ISK4-free graphs containing a are -colorable (2023).
October 23, 2026 restricted theorem
Qing Cui and Kaiyang Lan report that every diamond-free graph containing no subdivision of has chromatic number at most , 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.
Solutions 0
No solutions have been posted yet.