4-colorability of cycles union K₄s
Problem 3.1 · arXiv:2511.02892
Status open high confidence
Problem 3.1 asks whether the union of a disjoint-cycle graph $G$ and a disjoint union $H$ of $K_4$'s is 4-colourable — the $d=2$ special case of the general Strong Colouring Conjecture. Prior to the source paper, Dalal–McDonald–Shan (arXiv:2406.17723, June 2024) reduced the problem to a 3-colourability question on a more restricted class of graphs, but did not settle the conjecture. No paper published after November 2025 resolving the conjecture was found.
Reviewer notes. The conjecture is the d=2 special case of the Strong Colouring Conjecture (Alon, Fellows, 1980s). The 2024 paper arXiv:2406.17723 (Dalal–McDonald–Shan, 'A reduction of the cycles plus K4s problem') reduces it to a 3-colourability question on triangles-and-short-paths graphs, but the core question remains open; this paper predates the source paper and is presumably known to its authors. The source paper cites Haxell (2004, Combin. Probab. Comput.) as the primary reference. No post-2025 resolution found in an exhaustive web search.
Context
This is a special case of the general strong chromatic number question: if $G$ has maximum degree $d$ and $H$ is a disjoint union of $K_{2d}$'s, is $G\cup H$ $(2d)$-colourable? The quantity $2d$ would be best possible, and it is known that $G\cup H$ is $(3d-1)$-colourable when $H$ is a disjoint union of $K_{3d-1}$'s.
Source paper
Open problems of the 33rd Workshop on Cycles and Colourings
János Barát, Zdeněk Dvořák, Penny Haxell, František Kardoš, Borut Lužar, Alfréd Onderko, Jozef Rajník, Roman Soták, Nikolay Ulyanov · 2025-11-04
https://arxiv.org/abs/2511.02892