Conjecture that P₅-free graphs are path-perfect
Conjecture that P₅-free graphs are path-perfect
Let 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, . P₅-free path-perfectness conjecture. If is a -free graph, then 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
Sign in to submit a solution.
No solutions have been posted yet.