PaperlayerView exact revision on arXiv

Source-linked AI summary

Coloring graphs with no long induced path

Sang-il Oum

arXiv:2609.08847v3math.COcs.DM

TL;DR

Whether P_t-free graphs are polynomially χ-bounded remains open for t ≥6, while prior exponential bounds have base t−2. The paper combines two refinements of the Gyárfás path argument to lower that base to t−3 for every t ≥5.

  • Problem

    Whether P_t-free graphs are polynomially χ-bounded is open for every t ≥6, and prior bounds have exponential base t−2.

    Source: §1 · p. 1

  • Method

    The proof combines clique reduction with a large-small split inside a refinement of the Gyárfás path argument.

    Source: §1 · p. 2

  • Results

    For every t ≥5, the exponential base in the χ-bound for P_t-free graphs is lowered from t−2 to t−3, with a constant factor depending only on t.

    Source: §1 · p. 1

  • Takeaways & Limitations

    The result improves the exponential bound for every t ≥5 but does not address whether P_t-free graphs are polynomially χ-bounded.

    Source: §1 · p. 1

    The covered-set lemma requires every vertex of A to have a neighbor in S and its stated coloring and clique-reduction conditions for induced subgraphs of G[A].

    Source: §3 · p. 4

Abstract

from arXiv · show

Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gy\'arf\'as (1987) proved that every $P_t$-free graph $G$ satisfies $\chi(G)\le(t-1)^{\omega(G)-1}$, and Gravier, Ho\`ang, and Maffray (2003) improved this to $\chi(G)\le (t-2)^{\omega(G)-1}$ for $t\ge4$. We lower the base of the exponential by one: for every $t\ge5$, every $P_t$-free graph $G$ satisfies \[ \chi(G)\le 3\,(t-3)^{\omega(G)+4}. \] The proof combines two refinements of the Gy\'arf\'as path argument and was developed with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.

1. Introduction

For every t ≥5, the paper lowers the exponential base in a χ-bound for P_t-free graphs from t−2 to t−3. Its proof combines clique reduction with a large-small split in a refinement of the Gyárfás path argument.

1. Introduction

  • For every integer t ≥ 5, the exponential base t − 2 in the χ-bound for P_t-free graphs can be lowered to t − 3, at the cost of a constant factor depending only on t.Source: §1 · p. 1
  • Polynomial χ-boundedness remains unaddressed; the paper instead targets an improved exponential base, a question of interest mainly for t ≥6.The introduction notes that whether P_t-free graphs are polynomially χ-bounded is open for t ≥6.Source: §1 · p. 1
  • Theorem 2 supplies the graph-theoretic core: a clique-reducing set has complement colorable with B_k colors, yielding χ(G) ≤ F_k.Analyzing the sequence (F_k) gives Theorem 1.Source: §1 · p. 2
  • The classical path argument grows an induced path while choosing components that remain difficult to color, then stops one step earlier than the prior refinement.The construction maintains a component attached to the newest path vertex but not to earlier path vertices.Source: §1 · p. 2
  • Clique reduction reserves a low-cost-to-color complement in each component, while a large-small split separates components by clique number and controls the covered set.The small components are pairwise anticomplete; the large components leave a covered set whose neighborhoods see smaller cliques.Source: §1 · pp. 2–3
  • Combining the refinements changes the covered-set cost from c_{k−m−1}d^m to c_{k−m−1}L_m, making the loss summable with balanced m≈k/2.The paper tracks the resulting savings in its recurrence for Theorem 2.Source: §1 · p. 3

2. A rooted clique-reduction lemma

The rooted clique-reduction lemma bounds the chromatic number left after removing a set of clique number below r. Its path-based induction applies this bound to connected induced subgraphs attached to an induced path.

2. A rooted clique-reduction lemma

  • There is a set R ⊆ V(D) with ω(G[R]) < r and χ(D \ R) ≤ (t − ℓ − 3)a + b.The setting is a connected induced subgraph D attached to the end of an induced path of length ℓ, with earlier path vertices anticomplete to D.Source: §2 · p. 3
  • At ℓ = t − 3, each component of D \ A has clique number below r, where A is the neighborhood of the path endpoint in D.Pt-freeness makes each vertex of A complete or anticomplete to each such component; connectivity ensures each component has a neighbor in A.Source: §2 · p. 3
  • The proof chooses clique-reducing sets in the components of D \ A and combines them with A while keeping the union's clique number below r.The components are pairwise anticomplete, and the maximum-clique comparison with a component's maximum clique bounds any clique meeting both A and its selected set.Source: §2 · p. 3
  • For shorter paths, removing N(pℓ) ∩ V(D) and applying induction to components of the remainder yields the stated chromatic bound.If a remainder component exceeded the bound, a neighbor in the removed set would extend the path and permit the induction hypothesis.Source: §2 · p. 3

3. The covered-set lemma

The covered-set lemma bounds both the chromatic number of induced subgraphs and the cost of coloring after removing a clique-reducing set. Its induction uses a neighborhood split and a recurrence that improves on paying for every neighborhood separately.

3. The covered-set lemma

  • L_m obeys L_m = dL_{m−1} − L_{m−2} + 1 for m ≥ 2, with L_0 = 1 and L_1 = d + 1.The lemma also bounds L_m above by the sum of d^i from i = 0 to m.Source: §3 · p. 4
  • The sequences satisfy β_m = c + (d − 2)α_{m−1} + β_{m−1} and α_m = α_{m−1} + β_m, with α_0 = c and β_0 = b.The resulting bound is α_m = L_m c − p_m(c − b).Source: §3 · p. 4
  • χ(H) ≤ L_m c when ω(G[A]) ≤ q + m.More generally, each nonempty induced subgraph H of G[A] with clique number at most q + m has a clique-reducing set whose complement is β_m-colorable.Source: §3 · p. 4
  • The induction colors W with c colors and handles each component of H \ W by a clique-reducing set, reusing colors across the pairwise anticomplete remainders.W is the neighborhood in H of a vertex from S; the component bounds use the rooted lemma with path length 2.Source: §3 · pp. 4–5
  • Clique reduction keeps W in the complement of the removed set, allowing componentwise clique-reducing sets to be united without creating a new maximum clique.Without clique reduction, removing d neighborhoods would give α_m ≤ c + dα_{m−1}, costing about d^m c rather than L_m c.Source: §3 · p. 5

4. Proof of the main recurrence

The proof combines a Gyárfás path construction with two ways to bound its final connected subgraph. Clique reduction and a large-small component split yield the induction bounds used to establish χ(G) ≤ F_k.

4. Proof of the main recurrence

  • χ(G) ≤ F_k follows from a clique-reducing set with χ(G \ R) ≤ B_k and ω(G[R]) ≤ k − 1.Induction gives χ(G[R]) ≤ F_{k−1}, and F_{k−1} + B_k = F_k.Source: §4 · p. 5
  • The path construction produces an induced path u₁…u_{t−3} and a connected subgraph D attached to its endpoint, with χ(D) > F_{k−1} + T_k.D is disjoint from the earlier vertices' neighborhoods; the set A of endpoint neighbors in D and the components of D \ A set up the two bounds.Source: §4 · p. 5
  • Clique reduction gives a set R_D with ω(G[R_D]) < k and χ(D \ R_D) ≤ B_{k−1}, hence χ(D) ≤ F_{k−1} + B_{k−1}.This is the first of the two bounds on D.Source: §4 · p. 5
  • For the other bound, large components and vertices not adjacent to them induce a graph of clique number at most k − 1, while the small-component remainders are pairwise anticomplete.The construction selects a vertex in each large component and applies the covered-set lemma to the vertices of A adjacent to large components.Source: §4 · pp. 5–6
  • The large-small split gives χ(D) ≤ F_{k−1} + T_k, contradicting the path construction's lower bound χ(D) > F_{k−1} + T_k.Taking the better bound over the permitted choices of m establishes the contradiction.Source: §4 · pp. 5–6

5. Analysis of the recurrence

The recurrence analysis derives bounds from clique reduction and a second candidate recurrence, then combines them to control F_k by a constant times d^(k−1). It also records the role of AI tools in developing the proof arguments and the author’s responsibility for correctness.

5. Analysis of the recurrence

  • The analysis tracks nondecreasing sequences (F_k) and (B_k), with B_k≤F_k, and uses F_k=dF_(k−1)+T_k for k≥2.Using only the first candidate, it derives B_k≤(d−1)F_(k−1)+B_(k−1) and F_k≤dF_(k−1)+B_(k−1).Source: §5 · p. 6, §5.1 · p. 6

5.1. The clique-reduction bound.

  • Clique reduction alone gives F_k ≤ a_k and B_k ≤ a_k − a_(k−1), where a_0=0, a_1=1, and a_k=(t−2)a_(k−1)−a_(k−2).The recurrence bound is obtained without the large-small split.Source: §5.1 · p. 6

5.2. A quadratic bound.

  • For every 0 ≤ m ≤ k − 2 with q = k − m − 1, the second candidate in (2) gives Fk ≤ dFk−1 + Fm + LmFq ≤ dFk−1 + Fm + Fq.Source: §5.2 · p. 6

5.3. Combining two bounds.

  • F_k ≤ κ_d d^(k−1) with κ_d ≤ 3d^5 is the combined bound established in the proof of Theorem 1.The proof reduces the theorem to bounding F_k, then bounds the constant κ_d.Source: §5.3 · p. 7

Statement of AI use

  • Claude Fable 5.1 and GPT Pro produced proof arguments; the author simplified and rewrote them and takes full responsibility for mathematical correctness.Source: Statement of AI use · p. 7
Loading 2609.08847v3…