Paperlane

no. 9 · Thursday 5 November 2026

Optimal defective chromatic separation for clique blowups

Guillaume Lecomte

math.CO · v2 · 9 pp

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
pdf ↗ page arXiv:2609.17557 ↗