Conjecture that chromatic number is not bounded by a constant multiple of r(G)
Conjecture that chromatic number is not bounded by a constant multiple of r(G)
From papers
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.
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
Sign in to submit a solution.
No solutions have been posted yet.