Conjecture that P₅-free graphs are path-perfect

Let GG be a graph. A graph is path-perfect if its chromatic number equals the maximum chromatic number of a subgraph spanned by an odd cycle, that is, χ(G)=r(G)\chi(G)=r(G). P₅-free path-perfectness conjecture. If GG is a P5P_5-free graph, then GG is path-perfect. The source describes this as an even stronger conjecture than path-perfectness for the two preceding forbidden-subgraph classes; it remains open.

Sources & referencesView supporting material

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.