The cycle-free chromatic discrepancy conjecture

About 1 year old · traced to

Let GG be a graph. For an integer ℓ≥2\ell\ge 2, 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 φ(G)\varphi(G) denote the chromatic discrepancy of GG.

Cycle-free chromatic discrepancy conjecture. For every integer ℓ≥2\ell\ge 2, every Cℓ+1C_{\ell+1}-free graph GG satisfies

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

This is proposed as a weaker version of the locally ss-colourable conjecture, because every Cℓ+1C_{\ell+1}-free graph is locally ℓ\ell-colourable. The source explicitly states that this weaker form is open.

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.