Optimal χ-to-χᵈ ratio in K_{d+1} blowups
Problem 1.4 · arXiv:2504.01548
Status open high confidence
Problem 1.4 asks for the smallest constant $c$ such that $\chi(G) \leq c \cdot \chi^d(G \boxtimes K_{d+1})$ holds for all graphs $G$ and $d \geq 0$. The paper itself establishes the bounds $30/29 \leq c \leq 2$: the lower bound comes from an explicit counterexample to the original Guo--Kang--Zwaneveld equality conjecture, while the upper bound $c \leq 2$ is proved as Theorem 1.3. No subsequent work narrowing this gap was found in a thorough web search conducted in May 2026.
Reviewer notes. The paper was published in The Electronic Journal of Combinatorics 33(1), P1.17 (January 2026). Problem 1.4 is equivalent to determining the supremum of $\chi(G)/\chi^d(G \boxtimes K_{d+1})$ over all graphs $G$ and $d \geq 0$. The current bounds give $30/29 \leq c \leq 2$; no follow-up work narrowing this gap was found.
Context
Theorem 1.2 (for $d=2$) provides a graph showing that $c\geq\frac{30}{29}$ is necessary, while Theorem 1.3 gives the upper bound $c\leq 2$. A bootstrapped version of Theorem 1.2 further shows that assuming $\chi(G)$ or $d$ to be large cannot reduce the constant factor arbitrarily close to $1$.
Notes. The theorem environment statement is truncated to 'Determine' in the source; the full problem is reconstructed from the immediately preceding context.
Source paper
Defective coloring of blowups
Sergey Norin, Raphael Steiner · 2025-04-02
https://arxiv.org/abs/2504.01548