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

About 1 year old · traced to

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)>c⋅r(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.

References

Primary source

Ben Cameron and Alexander Clow, “On Gyárfás' Path-Colour Problem”, arXiv:2506.19100 (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.