Gyárfás' boundedness conjecture for graphs with odd-cycle chromatic number at most three

From papers

Let GG be a graph, and let r(G)r(G) denote the maximum chromatic number of a subgraph spanned by an odd cycle of GG, while χ(G)\chi(G) denotes the chromatic number of GG. Gyárfás' boundedness conjecture. There exists a constant kk (perhaps k=4k=4) such that if GG is a graph with r(G)3r(G)\leq 3, then χ(G)k\chi(G)\leq k. 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

No solutions have been posted yet.