Paperlane

no. 2 · Monday 26 October 2026

The chromatic number of $\{\mathrm{ISK}_4, \textup{diamond}\}$-free graphs

Qing Cui and Kaiyang Lan

math.CO

Abstract

An $\mathrm{ISK}_4$ is a graph that is isomorphic to a subdivision of $K_4$; a \textit{diamond} is $K_4$ minus one edge; and a \textit{bowtie} consists of two triangles sharing exactly one vertex. Lévêque, Maffray, and Trotignon~(2012) conjectured that every $\mathrm{ISK}_4$-free graph is $4$-colorable. Chen, Chen, Cui, Feng, and Liu~(2021) proved this for $\{\textup{diamond},\textup{bowtie}\}$-free graphs. We prove this conjecture for diamond-free graphs. Moreover, the bound is optimal.

comments
Comments are welcome!
fields
Combinatorics
pdf ↗ page arXiv:2610.32404 ↗