2025/06/23 by Ben Cameron, Alexander Clow, Cameron, Ben +1
Physics and Astronomy · Psychology · Engineering · #Color Science and Applications #Color perception and design #Advanced Theoretical and Applied Studies in Material Sciences and Geometry
paper · pdf · doi:10.48550/arxiv.2506.19100
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)log(8)/(7)(n). We prove that for all natural numbers r, there exists a graph G with r(G)≤ r and χ(G)≥ \lfloor(3r)/(2)\rfloor -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)+\binomt-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 2K2 or K2+2K1, then all H-free graphs are path-perfect.