no. 2 · Monday 26 October 2026
The chromatic number of $\{\mathrm{ISK}_4, \textup{diamond}\}$-free graphs
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