The strengthened cycle-free chromatic discrepancy conjecture

About 1 year old · traced to

Let GG be a graph. For an integer ℓ≥3\ell\ge 3, call GG Cℓ+1C_{\ell+1}-free if it contains no cycle of length exactly ℓ+1\ell+1 as a, not necessarily induced, subgraph. Let KℓK_{\ell} denote the complete graph on ℓ\ell vertices, and let φ(G)\varphi(G) denote the chromatic discrepancy of GG.

Strengthened cycle-free chromatic discrepancy conjecture. For every integer ℓ≥3\ell\ge 3, every Cℓ+1C_{\ell+1}-free graph G≠KℓG\ne K_{\ell} satisfies

φ(G)≥χ(G)−ℓ+1.\varphi(G)\ge \chi(G)-\ell+1.

The source presents this as a stronger conjecture motivated by the suspicion that equality in the weaker bound occurs only when ℓ=2\ell=2 or when GG is complete. Its status is not otherwise resolved in the supplied text.

References

Primary source

Timothée Corsini, Lucas Picasarri-Arrieta, Théo Pierron, François Pirot and Eileen Robinson, “Chromatic discrepancy of locally s-colourable graphs”, arXiv:2508.02985 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.