The strengthened cycle-free chromatic discrepancy conjecture

From papers

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 KK_{\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 GKG\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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.