Conjecture that chromatic number is not bounded by a constant multiple of r(G)
Let be the maximum chromatic number of a subgraph spanned by an odd cycle of a graph , and let be the chromatic number of . Linear separation conjecture. For every constant there exists a graph with
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.