On Gyárfás' Path-Colour Problem

In their 1997 paper titled ``Fruit Salad", Gyárfás posed the following conjecture: there exists a constant k such that if each path of a graph spans a 3-colourable subgraph, then the graph is k-colourable. It is noted that k=4 might suffice. Let r (G) be the maximum chromatic number of any subgraph H of G where H is spanned by a path. The only progress on this conjecture comes from Randerath and Schiermeyer in 2002, who proved that if G is an n vertex graph, then χ (G) r (G) ₈₇ (n). We prove that for all natural numbers r, there exists a graph G with r (G) r and χ (G) 3r2 -1. Hence, for all constants k there exists a graph with χ- r > k. Our proof is constructive. We also study this problem in graphs with a forbidden induced subgraph. We show that if G is K₁, ₓ-free, for t 4, then χ (G) (t-1) (r (G) +t-12-3). If G is claw-free, then we prove χ (G) 2r (G). Additionally, the graphs G where every induced subgraph G' of G satisfy χ (G') = r (G') are considered. We call such graphs path-perfect, as this class generalizes perfect graphs. We prove that if H is a forest with at most 4 vertices other than the claw, then every H-free graph G has χ (G) r (G) +1. We also prove that if H is additionally not isomorphic to 2K₂ or K₂+2K₁, then all H-free graphs are path-perfect.