Conjecture that chromatic number is not bounded by a constant multiple of r(G)

From papers

Let r(G)r(G) be the maximum chromatic number of a subgraph spanned by an odd cycle of a graph GG, and let χ(G)\chi(G) be the chromatic number of GG. Linear separation conjecture. For every constant c>0c>0 there exists a graph GG with

χ(G)>cr(G).\chi(G)>c\cdot r(G).

The source proposes this as an improvement of its main lower-bound result. It is stated as a conjecture for future work, and no resolution is given.

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

Ben Cameron and Alexander Clow, “On Gyárfás' Path-Colour Problem”, arXiv:2506.19100 (2025).

Solutions 0

No solutions have been posted yet.