{
  "id": "2506.19100",
  "version": "v1",
  "published": "2025-06-23T20:23:07.000Z",
  "updated": "2025-06-23T20:23:07.000Z",
  "title": "On Gyárfás' Path-Colour Problem",
  "authors": [
    "Ben Cameron",
    "Alexander Clow"
  ],
  "comment": "30 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "In their 1997 paper titled ``Fruit Salad\", Gy\\'{a}rf\\'{a}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 $\\chi(G) \\leq r(G)\\log_{\\frac{8}{7}}(n)$. We prove that for all natural numbers $r$, there exists a graph $G$ with $r(G)\\leq r$ and $\\chi(G)\\geq \\lfloor\\frac{3r}{2}\\rfloor -1$. Hence, for all constants $k$ there exists a graph with $\\chi - 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\\geq 4$, then $\\chi(G) \\leq (t-1)(r(G)+\\binom{t-1}{2}-3)$. If $G$ is claw-free, then we prove $\\chi(G) \\leq 2r(G)$. Additionally, the graphs $G$ where every induced subgraph $G'$ of $G$ satisfy $\\chi(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 $\\chi(G) \\leq 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-06-23T20:23:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15",
      "05C38"
    ],
    "keywords": [
      "path-colour problem",
      "class generalizes perfect graphs",
      "free graph",
      "maximum chromatic number",
      "induced subgraph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}