Abstract
A graph G is H -free if it has no induced subgraph isomorphic to H. We prove that a P5 -free graph with clique number ω≥ 3 has chromatic number at most ωlog2(ω) . The best previous result was an exponential upper bound (5 / 27) 3 ω , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for P5 , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for P5 -free graphs, and our result is an attempt to approach that.
Original language | American English |
---|---|
Pages (from-to) | 845-852 |
Number of pages | 8 |
Journal | Combinatorica |
Volume | 43 |
Issue number | 5 |
DOIs | |
State | Published - Oct 2023 |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics
Keywords
- Chromatic number
- Induced subgraphs