Fractionally colouring P₅-free graphs

2025/10/07 by Nguyen, Tung H.
#05C35 #05C55 #05C69 #05C72 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.05724

Abstract

We obtain some d≥2 such that every graph G with no induced copy of the five-vertex path P₅ has at most α(G)ω(G)^d vertices. This ``off-diagonal Ramsey'' statement implies that every such graph G has fractional chromatic number at most ω(G)^d, and is another step towards the polynomial Gyárfás-Sumner conjecture for P₅. The proof uses the recent Erdős-Hajnal result for P₅ and adapts a decomposition argument for P₅-free graphs developed by the author in an earlier paper.

Citations

• On polynomially high-chromatic pure pairs
• Trees and near-linear stable sets
• Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
• Induced subgraph density. VI. Bounded VC-dimension
• Induced subgraph density. VII. The five-vertex path
• Polynomial bounds for chromatic number. III. Excluding a double star
• A survey of χ-boundedness
• A survey of χ‐boundedness
• The Ramsey number R (3, t ) has order of magnitude t 2 /log t

Related

• Bounding the fractional chromatic number of K_Δ-free graphs
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
• Triangle-free d-degenerate graphs have small fractional chromatic number
• The Fractional Chromatic Number of Triangle-free Graphs with Δ≤ 3
• A new variant of the Erdős-Gyárfás problem on K₅