Skip to content
DraconiticResearch
Search Sources API
190,839 studies31 sourcesUpdated 58 min ago
PreprintCC BY 4.0arXiv

An improved lower bound for the blowup defective chromatic separation constant

  • Guillaume Lecomte
Open at sourcePDFDOICite

Abstract

For a graph G and an integer d ≥ 0, let χd(G) denote the d-defective chromatic number, and let G boxtimes Kd+1 be the (d+1)-fold clique blowup of G. Norin and Steiner disproved the conjecture χ(G) = χd(G boxtimes Kd+1) of Guo, Kang and Zwaneveld by exhibiting, for infinitely many d, graphs with χ(G) ≥ (30/29) χd(G boxtimes Kd+1), and they proved the universal upper bound χ(G) ≤ 2 χd(G boxtimes Kd+1). Writing Cd = supG χ(G)/χd(G boxtimes Kd+1) and C* = supd Cd, their results give C* ∈ [30/29, 2]. We improve the lower bound: we exhibit an explicit 40-vertex graph W with χ(W) = 11 and χ2(W boxtimes K3) = 10, so that C* ≥ C2 ≥ 11/10 > 30/29, already at the smallest defect for which such a separation is possible, namely d = 2. All parameters are established by the proofs; the only computer-assisted input, the non-list-colourability of a certain 30-vertex, 10-colour list instance (B,L), is certified by an independently checkable DRAT refutation.

Related

  1. Defective chromatic polynomials
    Shamil Asgarli, Tamsen Whitehead McGinley, Nicholas Xue
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Analysis of blowup masses in constant-coefficient Toda systems: W-invariants and Weyl orbits
    Zhaohu Nie
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv
  3. An improved upper bound on the chromatic number of the n-dimensional sphere
    A. I. Bikeev, V. A. Voronov, A. M. Raigorodskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Explicit and logarithmically improved chromatic bounds for (P2∪ P3)-free graphs
    Lizhong Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Improved bounds on the b-chromatic number using the independence and chromatic numbers
    Manouchehr Zaker
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lecomte2026improved,
  title = {{An improved lower bound for the blowup defective chromatic separation constant}},
  author = {Guillaume Lecomte},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.17557},
  eprint = {2609.17557},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.17557},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - An improved lower bound for the blowup defective chromatic separation constant
AU  - Guillaume Lecomte
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.17557
UR  - https://arxiv.org/abs/2609.17557
AB  - For a graph G and an integer d ≥ 0, let χ^d(G) denote the d-defective chromatic number, and let G boxtimes K_d+1 be the (d+1)-fold clique blowup of G. Norin and Steiner disproved the conjecture χ(G) = χ^d(G boxtimes K_d+1) of Guo, Kang and Zwaneveld by exhibiting, for infinitely many d, graphs with χ(G) ≥ (30/29) χ^d(G boxtimes K_d+1), and they proved the universal upper bound χ(G) ≤ 2 χ^d(G boxtimes K_d+1). Writing C_d = sup_G χ(G)/χ^d(G boxtimes K_d+1) and C^* = sup_d C_d, their results give C^* ∈ [30/29, 2]. We improve the lower bound: we exhibit an explicit 40-vertex graph W with χ(W) = 11 and χ^2(W boxtimes K_3) = 10, so that C^* ≥ C_2 ≥ 11/10 > 30/29, already at the smallest defect for which such a separation is possible, namely d = 2. All parameters are established by the proofs; the only computer-assisted input, the non-list-colourability of a certain 30-vertex, 10-colour list instance (B,L), is certified by an independently checkable DRAT refutation.
ER  -