Polynomial $\chi$-boundedness for excluding $P_5$

Tung H. Nguyen

arxiv: 2512.24907 · v3 · submitted 2025-12-31 · 🧮 math.CO

Polynomial chi-boundedness for excluding P₅

Tung H. Nguyen This is my paper

Pith reviewed 2026-05-16 18:28 UTC · model grok-4.3

classification 🧮 math.CO

keywords P5-free graphschromatic numberclique numberinduced pathsGyárfás conjectureErdős-Hajnal conjecturequasirandomnessdensity increment

0 comments

The pith

Graphs without an induced P5 have chromatic number at most a polynomial in their clique number.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that forbidding an induced five-vertex path forces the chromatic number to grow at most polynomially with the size of the largest clique. This settles a question posed by Gyárfás in 1985. The argument develops a chromatic density framework built on quasirandomness and density-increment steps. These tools reduce the problem to the known Erdős-Hajnal property for P5-free graphs. A reader cares because the result shows that one small forbidden induced subgraph can impose a strong quantitative link between local clique structure and global coloring.

Core claim

Chromatic number is polynomially bounded by clique number for graphs with no induced P5. The deduction follows from the Erdős-Hajnal result for P5 via the newly introduced chromatic density framework involving chromatic quasirandomness and chromatic density increment.

What carries the argument

The chromatic density framework, which defines chromatic quasirandomness and chromatic density increment to deduce the polynomial bound from the Erdős-Hajnal result for P5.

If this is right

The chromatic number of every P5-free graph is bounded by a polynomial in its clique number.
The polynomial χ-boundedness conjecture holds for the specific forbidden induced subgraph P5.
The chromatic density framework supplies a general method for converting qualitative Erdős-Hajnal statements into quantitative polynomial bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same framework may yield polynomial bounds for other small forbidden induced paths once their Erdős-Hajnal properties are known.
Polynomial χ-boundedness often implies polynomial-time approximation algorithms for coloring; the same may hold here.
The approach could link to broader questions about how induced-subgraph restrictions control Ramsey-type growth rates.

Load-bearing premise

The chromatic density framework, including its quasirandomness and increment properties, correctly permits deduction of the polynomial bound from the known Erdős-Hajnal result for P5.

What would settle it

A sequence of P5-free graphs in which chromatic number grows faster than any fixed polynomial of the clique number would disprove the claim.

read the original abstract

Resolving a 1985 open problem of Gy\'arf\'as, we prove that chromatic number is polynomially bounded by clique number for graphs with no induced five-vertex path $P_5$. Our approach introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erd\H{o}s-Hajnal result for $P_5$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This abstract claims to settle Gyárfás's 1985 question with a new chromatic density framework that reduces the polynomial bound to the known Erdős-Hajnal property for P5-free graphs.

read the letter

The main takeaway is that the paper asserts a polynomial bound on chromatic number in terms of clique number for induced-P5-free graphs, which would close a long-standing open problem if the argument holds. They build a chromatic density framework using chromatic quasirandomness and density increments to make the reduction from the existing Erdős-Hajnal result. This approach is the actual novelty, and it has the merit of not starting from scratch but instead connecting two established lines of work in a direct way. The abstract presents the deduction as straightforward once the framework is in place, which is a reasonable strategy for this type of structural question. The clear limitation is that only the abstract is available, so the definitions of the new terms and the precise steps in the increment argument cannot be checked for gaps or hidden assumptions. Without those details it is impossible to confirm whether the framework actually delivers the polynomial bound cleanly or whether some step relies on an unstated property of P5-free graphs. This work sits squarely in structural graph theory for people who track χ-boundedness results and forbidden induced subgraphs. A reader who already knows the Erdős-Hajnal side would see the value in the proposed bridge. It deserves peer review so the framework can be examined by specialists who can test the definitions and the deduction against the full text.

Referee Report

1 major / 0 minor

Summary. The manuscript claims to resolve Gyárfás' 1985 open problem by proving that the chromatic number of P_5-free graphs is polynomially bounded in terms of the clique number. The proof introduces a chromatic density framework based on chromatic quasirandomness and chromatic density increment, from which the polynomial bound is deduced using the known Erdős-Hajnal property for P_5-free graphs.

Significance. If correct, the result would be a significant advance in χ-boundedness theory, as it settles the question for the first induced path of length greater than 3. The new framework concepts could potentially apply to other hereditary classes with known Erdős-Hajnal properties.

major comments (1)

[Abstract] Abstract: the assertion that the polynomial bound follows from the new framework and the Erdős-Hajnal result for P_5 cannot be evaluated, as the definitions of chromatic quasirandomness and chromatic density increment, together with the deduction steps, are not supplied in the provided text.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the need for clarity on how the main result is deduced. We address the comment point by point below.

read point-by-point responses

Referee: [Abstract] Abstract: the assertion that the polynomial bound follows from the new framework and the Erdős-Hajnal result for P_5 cannot be evaluated, as the definitions of chromatic quasirandomness and chromatic density increment, together with the deduction steps, are not supplied in the provided text.

Authors: The abstract is a concise summary of the paper's main contribution and approach. The full definitions of chromatic quasirandomness and chromatic density increment are introduced and developed in Section 2 of the manuscript, while the chromatic density increment argument and the deduction of the polynomial bound from the known Erdős-Hajnal property for P_5-free graphs are carried out in detail in Section 3. These sections supply the precise statements, lemmas, and proof steps needed to evaluate the claim. We are happy to expand the abstract slightly if the referee finds that helpful, but the current length is standard for the journal. revision: no

Circularity Check

0 steps flagged

No circularity detected from available abstract

full rationale

The abstract presents the result as a deduction of polynomial χ-boundedness from the independently known Erdős-Hajnal property for P5-free graphs, via a newly introduced chromatic density framework. No equations, definitions, or derivation steps are supplied in the provided text, so no load-bearing reduction to self-definition, fitted inputs, or self-citation chains can be exhibited. The derivation is therefore self-contained relative to the given information, with the central claim resting on an external result rather than internal circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

Abstract-only review; the central argument rests on the known Erdős-Hajnal result for P5 and on two newly introduced concepts (chromatic quasirandomness and chromatic density increment) whose precise definitions and independence are not supplied.

axioms (1)

domain assumption Erdős-Hajnal result holds for P5
The proof deduces the polynomial bound from this result as stated in the abstract.

invented entities (2)

chromatic quasirandomness no independent evidence
purpose: Component of the chromatic density framework for analyzing coloring properties
New concept introduced in the framework; no independent evidence or prior reference given in abstract.
chromatic density increment no independent evidence
purpose: Incremental step within the chromatic density framework
New technique introduced to support the deduction; no independent evidence supplied.

pith-pipeline@v0.9.0 · 5321 in / 1425 out tokens · 48435 ms · 2026-05-16T18:28:49.793740+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our approach introduces a chromatic density framework involving chromatic quasirandomness and chromatic density increment, which allows us to deduce the desired statement from the Erdős–Hajnal result for P5.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 2.6 … pure pair versus (ε,χ)-dense induced subgraph … Gyárfás path argument

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Ramsey-type $\chi$-bounds for $\chi$-bounded graph classes
math.CO 2026-05 unverdicted novelty 8.0

For graphs with no induced T (forest with broom components or any forest) and no induced H (complete multipartite or bipartite), χ(G) is at most C times R(α(H), ω(G)+1) for a constant C depending only on T and H.