The chromatic number of $\{\mathrm{ISK}_4, \textup{diamond}\}$-free graphs
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 and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.32404
curl -X POST /api/v1/records/arxiv/2610.32404/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.32404/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'