Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path
A graph G is H-free if it has no induced subgraph isomorphic to H. We prove that a $P_5$-free graph with clique number $\omega\ge 3$ has chromatic number at most $\omega^{\log_2(\omega)}$. The best previous result was an exponential upper bound $(5/27)3^{\omega}$, due to Esperet, Lemoine, Maffray, a...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer
2023
|