P_t-free graphs: the Gyárfás path argument (χ-boundedness + minimal-counterexample cycle surgery)

Statement

For a graph $H$, write "$G$ is $H$-free" if $G$ has no induced subgraph isomorphic to $H$. For $t\ge1$, $P_t$ denotes the path on $t$ vertices, and $G$ is $P_t$-free if it contains no induced copy of $P_t$ — i.e. every set of $t$ vertices that forms a path in $G$ must have at least one extra ("chord") edge among them. $P_t$-freeness is a *restricted graph class* hypothesis: it does not forbid long paths as subgraphs, only as *induced* subgraphs, so $P_t$-free graphs can still have huge diameter — what is forbidden is a chordless walk of that length.

This page documents the technique family built around forbidding a long induced path, which splits into two related but distinct strands, both anchored on the same "Gyárfás path" idea (arxiv.org/pdf/1812.07500, Section 3, fetched directly):

Strand A — χ-boundedness (Gyárfás–Sumner conjecture, the origin of the technique). An ideal (hereditary class) $\mathcal I$ is χ-bounded if there is a function $f$ with $\chi(G)\le f(\omega(G))$ for every $G\in\mathcal I$ ($\chi$ = chromatic number, $\omega$ = clique number); $f$ is a *χ-binding function*. The Gyárfás–Sumner conjecture (Gyárfás 1975, Sumner 1981, independently — en.wikipedia.org/wiki/Gyárfás–Sumner_conjecture; also arxiv.org/pdf/1812.07500 §3, statement 3.1): *for every forest $H$, the class of $H$-free graphs is χ-bounded.* Only forests can have this property — any $H$ containing a cycle of length $g$ fails, because Erdős's random construction gives triangle-free graphs of girth $>g$ and arbitrarily large $\chi$, and these are automatically $H$-free (arxiv.org/pdf/1812.07500 §3, paragraph before 3.1). Gyárfás proved the path case (arXiv-predates-arXiv; Gyárfás 1985/1987, per the survey's footnote crediting Gerlits for the triangle-free case and Lovász for the general case, first published proof in Gyárfás's "Problems from the world surrounding perfect graphs"):

> 3.4 (Gyárfás). Every path is χ-bounding: for every $t$, the class of $P_t$-free graphs is χ-bounded.

The explicit χ-binding function from Gyárfás's original argument is exponential in $\omega$: $\chi(G) \le (t-1)^{\omega(G)-1}$ for $P_t$-free $G$ (widely cited secondary-source formula; not independently verified against Gyárfás's own 1985 text this session — flagged, see provenance). This exponential bound stood as the state of the art for the *general* $t$ case for decades; only for small fixed $t$ has it since been sharpened (see Facts).

Strand B — minimal-counterexample cycle surgery on $P_t$-free graphs. A separate, more recent line of work (2021–2024) uses $P_t$-freeness not for a χ-bound but as a *structural* hypothesis that keeps a minimal-counterexample case analysis finite: e.g. confirming the Erdős–Gyárfás power-of-two-cycle conjecture (Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle) on $P_8$-free and $P_{10}$-free graphs — see Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs for the full technique writeup. This strand reuses the *same* combinatorial primitive as Strand A (grow a long induced path by splicing in fresh off-path neighbours forced by a degree condition) but points it at a different target invariant (a short cycle, not a small chromatic number).

Facts

- Only forests can be χ-bounding: this is forced by Erdős's 1959 probabilistic construction of triangle-free, high-girth, high-χ graphs (arxiv.org/pdf/1812.07500 §2–3) — so "forbid an induced path/tree" is essentially the *only* single-forbidden-subgraph route to χ-boundedness; forbidding a graph with a cycle never works. - The Gyárfás–Sumner conjecture for general trees is still open (arxiv.org/pdf/1812.07500 §3, "for trees the conjecture is a lot tougher, and it remains open"; en.wikipedia.org/wiki/Gyárfás–Sumner_conjecture confirms open as of 2026). Known confirmed cases beyond paths: stars (easy Ramsey argument), brooms (Gyárfás), subdivisions of stars (Scott, [105] in the survey), trees of radius 2 (Gyárfás–Szemerédi–Tuza 1980s for triangle-free case; Kierstead–Penrice 1994 general case), and several further sporadic tree families via a "levelling/grading" method (Scott–Seymour–Spirkl, arxiv.org/pdf/1812.07500 §3, results 3.5–3.6). A weaker statement — forbidding a *subdivision* of a fixed tree $T$ (rather than $T$ itself) — is fully proved for all trees (3.3 in the survey). - Quantitative sharpening only exists for small $t$, and this is an *active current research frontier*: - $t=4$ ($P_4$-free): $P_4$-free graphs are exactly the cographs, which are perfect, so $\chi=\omega$ — the trivial best-possible χ-binding function. - $t=5$ ($P_5$-free): Esperet–Lemoine–Maffray–Morel gave an exponential bound $\chi \le \tfrac{5}{27}3^{\omega}$; Scott–Seymour–Spirkl improved this to the near-polynomial $\chi \le \omega^{\log_2\omega}$ for $\omega\ge3$ (arXiv:2110.00278, "Polynomial bounds for chromatic number IV", abstract fetched directly); a 1985 Gyárfás problem asking for a genuinely *polynomial* bound on $P_5$-free graphs was resolved (positively) very recently — arXiv:2512.24907, abstract verbatim: "Resolving a 1985 open problem of Gyárfás, we prove that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path $P_5$." - General $t$, mixed hypotheses: Nguyen–Scott–Seymour, "Polynomial bounds for chromatic number VIII: excluding a path and a complete multipartite graph" (arXiv:2303.11766, abstract fetched directly): *"For every path $H$, and every integer $d$, there is a polynomial $f$ such that every graph $G$ with chromatic number greater than $f(t)$ either contains $H$ as an induced subgraph, or contains as a subgraph the complete $d$-partite graph with parts of cardinality $t$"* — i.e. once you additionally forbid a large complete multipartite subgraph, the $P_t$-free χ-bound becomes fully polynomial; this is part of the "Polynomial bounds for chromatic number" series (papers I–VIII+) systematically chasing polynomial χ-binding functions across the Gyárfás–Sumner landscape. - The same "splice a long induced path out of a degree condition" primitive is reused for a structurally different goal: proving the Erdős–Gyárfás power-of-2-cycle conjecture (Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle) on $P_8$-free graphs (Gao–Shan, arXiv:2109.01277) and $P_{10}$-free graphs (Hu–Shen, arXiv:2308.05675), later pushed to $P_{12}$/$P_{13}$-free (arXiv:2410.22842) — full writeup at Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs. There the induced path is grown from a chordless hole plus forced off-hole neighbours (minimum-degree $\ge3$ forces an escape at every hole vertex), and $P_t$-freeness caps how long that spliced path can get before it must instead close into one of two specific short cycles (length 4 or 8). - Algorithmic reuse ("Gyárfás path argument" as a separator lemma): the same construction gives an efficient *balanced separator*: given an $n$-vertex $P_t$-free graph, in polynomial time one can find a set $P$ of at most $t-1$ vertices such that every connected component of $G - N[P]$ has at most $n/2$ vertices (per WebSearch summary of arXiv:1804.04077 and the Dagstuhl paper "Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument", drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.93 / dl.acm.org/doi/10.1145/3636422, titles and abstract-snippet only, not independently fetched in full this session). This underlies subexponential- and quasi-polynomial-time algorithms for Maximum (Weight) Independent Set on $P_t$-free graphs, and the paper cited generalizes the exact same combinatorial move from "no long induced path" to "no long induced claw" (a structurally broader forbidden pattern), showing the technique's reusable core is the *path-growing/graph-shrinking induction*, not paths specifically.

Technique

How the Gyárfás path argument works, mechanically (Strand A — χ-boundedness; transcribed from the proof sketch of 3.4 in arxiv.org/pdf/1812.07500, read directly via full-text PDF extraction):

1. Reduce to a per-component lemma with two hypotheses. Fix $\ell$ (the forbidden path length) and prove, by induction on $\ell$: *if $G$ is connected, $\chi(N(v))\le c$ for every vertex $v$, and there is some vertex $v_0$ from which no $\ell$-vertex induced path starts, then $\chi(G)$ is bounded by a function of $c,\ell$ alone.* 2. Base the induction on the "no long path from $v_0$" hypothesis. Let $v_0$ be the vertex with no long induced path starting at it. Since $\chi(N(v_0))\le c$ by hypothesis, all the "coloring danger" is pushed into the components of $G$ minus $v_0$'s closed neighbourhood. For each such component $H$, some neighbour $u\in N(v_0)$ has a neighbour in $H$ — and crucially, because $v_0$ has no $\ell$-vertex induced path starting from it, $u$ can have no $(\ell-1)$-vertex induced path starting from it *within* $H\cup\{v_0\}$ (otherwise prepending $v_0u\cdots$ would give an $\ell$-vertex induced path from $v_0$). This hands the smaller instance (path bound $\ell-1$) to the inductive hypothesis on $H\cup\{u\}$, bounding $\chi(H)$. 3. Sum over components. Since every component off $N[v_0]$ has bounded chromatic number and $N(v_0)$ itself has bounded chromatic number, $\chi(G)$ is bounded — closing the induction on $\ell$. 4. Outer induction on clique number $\omega$. With $\ell$ now fixed, induct on $\kappa=\omega(G)$: for a $P_\ell$-free graph $G$ with $\omega(G)\le\kappa$, the inductive hypothesis (on smaller $\kappa$) bounds $\chi(N(v))$ for every vertex $v$ (a neighbourhood of $v$ in a $K_{\kappa+1}$-free graph has clique number $\le\kappa-1$). Feed that bound as the "$c$" into the Step-1 lemma; since $G$ is $P_\ell$-free, *every* vertex trivially satisfies "no $\ell$-vertex induced path starts here," so the lemma applies directly to every component, giving a global χ-bound. 5. Why it works (the mechanism): the argument never inspects global structure — it only ever asks "how far can an induced path be walked from a fixed starting vertex before it must stop (because it hit the forbidden length or ran out of graph)?" Forbidding $P_\ell$ caps that walk length uniformly, and the induction converts *a uniform cap on induced-path-growth* into *a uniform cap on chromatic number*, one recursive layer (path length) and one recursive layer (clique number) at a time. This is a clean instance of the general "local structural restriction $\Rightarrow$ global coloring bound via nested induction" pattern; the price is that naive path-growing induction produces an *exponential* bound in $\omega$ (each layer of the $\kappa$-induction can multiply the constant), which is why sharpening to polynomial bounds (Strand facts above) needs entirely different, heavier machinery (chromatic density/quasirandomness arguments, "templates," "levellings/gradings" — arxiv.org/pdf/1812.07500 §3, describing the more advanced proofs for radius-2 trees and beyond). 6. A closely related "levelling" variant (used for hole-length χ-bounds, arxiv.org/pdf/1812.07500 result 6.1, explicitly credited there as "this is Gyárfás's argument to prove 3.4" in disguise): take a BFS levelling $L_0,L_1,\dots$ from a vertex, focus on the level $L_j$ of maximum χ, and greedily walk backward through $L_{j-1},L_{j-2},\dots$ picking a fresh neighbour $v_i$ at each step whose removal still leaves a high-χ component $A_{i+1}$ in $L_j$ — after $\ell$ steps this produces an *explicit* induced path $v_0v_1\cdots v_{\ell-1}$ of length $\ge\ell$, contradicting the path-freeness/hole-length hypothesis. This "walk backward through levels, greedily deleting each new vertex's neighbourhood from the surviving high-χ set, and read off the deletion order as an induced path" move is the general-purpose reusable primitive — it appears again nearly verbatim in the Strand-B cycle-surgery proofs (see Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs step 5, "splice arcs of the hole with off-hole neighbour paths into one long induced path").

WHEN this technique applies: whenever (a) the target class is defined by forbidding one or more induced paths (or, in Strand B, a chordless cycle/hole plus a path-length cap), (b) there is some *auxiliary quantity that decreases along the path* (chromatic number of the remaining graph in Strand A; the "how far the escape-neighbour chain can run before it must close up" bookkeeping in Strand B), and (c) a minimum-degree or minimum-χ hypothesis is available to force new vertices to attach at each step (a vertex of high χ or high degree must have "somewhere to go" beyond what's already been used). Without a forcing hypothesis of type (c), there is nothing to guarantee the path/escape-chain can be extended at all, and the induction stalls.

WHY it works (for recombination): forbidding an *induced* path (rather than a subgraph path, which is nearly always present) is a genuinely weak-looking hypothesis, but it interacts extremely well with induction because "no induced $P_\ell$ from $v$" is a *local, checkable, monotone-in-$\ell$* condition that composes cleanly under vertex deletion — deleting vertices can only shorten induced paths, never lengthen them, so the induction hypothesis transfers automatically to subgraphs. This is the general reason forbidden-induced-subgraph hypotheses (as opposed to forbidden-subgraph or forbidden-minor hypotheses) are so productive for this style of proof: hereditary classes are closed under exactly the operation (vertex deletion) the induction needs.

Related

- Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the open Erdős–Gyárfás power-of-2-cycle conjecture (min-degree-3 $\Rightarrow$ cycle of length $4,8,16,\dots$); confirmed on several $P_t$-free restricted classes via the Strand-B cycle-surgery variant of this technique. - Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs — full worked proof technique for the $P_8$-free and $P_{10}$-free confirmations of Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle; the "splice hole-arcs with off-hole neighbour chains into a long induced path" step is the Strand-B instance of the Gyárfás path primitive documented on this page. - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often and Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) — sibling power-of-2-cycle / cycle-length-sum problems on *unrestricted* (non-$P_t$-free) graphs of large chromatic number, resolved by Liu–Montgomery's completely different sublinear-expander machinery — a useful contrast showing the $P_t$-free route needs a lighter, more combinatorial tool than the general case. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — the general proof-by-contradiction skeleton (assume a smallest violating instance, derive structural constraints) that Strand B wraps around the path-growing primitive. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — a related but mechanistically distinct extremal/potential-function technique (used e.g. for cubic planar Erdős–Gyárfás confirmations); shares the "maximize/minimize a secondary invariant" flavor with the "good hole" extremal choice in Strand B but is not the same primitive.