no. 9 · Thursday 5 November 2026
Optimal defective chromatic separation for clique blowups
Abstract
Guo, Kang and Zwaneveld conjectured that colouring the \((d+1)\)-clique blowup of a graph with defect \(d\) requires as many colours as colouring the graph properly. Norin and Steiner refuted this, proved that the two chromatic numbers differ by at most a factor of two, and asked for the exact constant; the best separation known was \(11/10\). We prove that the constant is exactly two for every fixed defect \(d\ge 2\). Every rational ratio in \([1,2)\) is attained, by graphs whose clique number and fractional chromatic number equal the defective parameter: the separation is invisible to the standard lower bounds. The engine is an exact transfer theorem: a weighted list-colouring obstruction spread over an arbitrary auxiliary graph yields prescribed defective and ordinary chromatic numbers; Kneser graphs then give sharpness. A 29-vertex graph with defective parameter four and chromatic number five answers Norin's Barbados question at the smallest possible defect and palette.
- comments
- 9 pages, 2 figures. Revised version establishing the optimal separation factor of two for every fixed defect at least two, an exact transfer theorem, and a 29-vertex counterexample
- fields
- Combinatorics, Optimization and Control