Gyárfás' boundedness conjecture for graphs with odd-cycle chromatic number at most three
Gyárfás' boundedness conjecture for graphs with odd-cycle chromatic number at most three
Let be a graph, and let denote the maximum chromatic number of a subgraph spanned by an odd cycle of , while denotes the chromatic number of . Gyárfás' boundedness conjecture. There exists a constant (perhaps ) such that if is a graph with , then . This is the main problem discussed in the paper and is attributed to Gyárfás; the best progress cited is the logarithmic upper bound of Randerath and Schiermeyer, and the conjecture remains open.
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.