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

About 1 year old · traced to

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.

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.