On Gyárfás' Path-Colour Problem

Abstract

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 $\ddot{I}‡(G)\le r(G){\log }_{\frac{8}{7}}(n)$. We prove that for all natural numbers $r$, there exists a graph $G$ with $r(G)\le r$ and $\ddot{I}‡(G)\ge \lfloor \frac{3r}{2}\rfloor -1$. Hence, for all constants $k$ there exists a graph with $\ddot{I}‡-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_{1,t}$-free, for $t\ge 4$, then $\ddot{I}‡(G)\le (t-1)(r(G)+(\genfrac{}{}{0ex}{}{t-1}{2})-3)$. If $G$ is claw-free, then we prove $\ddot{I}‡(G)\le 2r(G)$. Additionally, the graphs $G$ where every induced subgraph $G^{\prime }$ of $G$ satisfy $\ddot{I}‡(G^{\prime })=r(G^{\prime })$ 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 $\ddot{I}‡(G)\le r(G)+1$. We also prove that if $H$ is additionally not isomorphic to $2K_2$ or $K_2+2K_1$, then all $H$-free graphs are path-perfect.

30 pages, 5 figures