Polynomial bounds for chromatic number. IV: A near-polynomial bound for excluding the five-vertex path (Q6081401): Difference between revisions

A graph \(G\) is \(P_5\)-free if \(G\) has no induced subgraph isomorphic to \(P_5\). The authors show that a \(P_5\)-free graph with clique number \(\omega \geq 3\) has the near-polynomial upper bound \(\omega ^ {\log_2\omega}\) on its chromatic number. The best previous known bound was an exponential upper bound \((5/27)3^\omega\), due to \textit{L. Esperet} et al. [Discrete Math. 313, No. 6, 743--754 (2013; Zbl 1260.05056)]. \par A polynomial bound would imply that the well-known conjecture of Erdős-Hajnal for which \(P_5\) is the smallest open case.