Optimal defective chromatic separation for clique blowups

arXiv:2609.17557 · math.CO, math.OC · Submitted 2026-07-20 · Read on arXiv

math.CO, math.OC

Submitted: 2026-07-20

Updated: 2026-11-04

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

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

Terminology

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 at least 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.

Sources

Related papers