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.
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.