Optimal defective chromatic separation for clique blowups
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality