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)log8/7(n). We prove that for all natural numbers r, there exists a graph G with r(G)≤ r and χ(G)≥ 3r/2 -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 K1,t-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.