Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path
Alex Scott, Paul Seymour, Sophie Spirkl
Abstract
Abstract A graph G is H -free if it has no induced subgraph isomorphic to H . We prove that a $$P_5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>P</mml:mi><mml:mn>5</mml:mn></mml:msub></mml:math> -free graph with clique number $$\omega \ge 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ω</mml:mi><mml:mo>≥</mml:mo><mml:mn>3</mml:mn></mml:mrow></mml:math> has chromatic number at most $$\omega ^{\log _2(\omega )}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>ω</mml:mi><mml:mrow><mml:msub><mml:mo>log</mml:mo><mml:mn>2</mml:mn></mml:msub><mml:mrow><mml:mo>(</mml:mo><mml:mi>ω</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:msup></mml:math> . The best previous result was an exponential upper bound $$(5/27)3^{\omega }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mn>5</mml:mn><mml:mo>/</mml:mo><mml:mn>27</mml:mn><mml:mo>)</mml:mo></mml:mrow><mml:msup><mml:mn>3</mml:mn><mml:mi>ω</mml:mi></mml:msup></mml:mrow></mml:math> , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for $$P_5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>P</mml:mi><mml:mn>5</mml:mn></mml:msub></mml:math> , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for $$P_5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>P</mml:mi><mml:mn>5</mml:mn></mml:msub></mml:math> -free graphs, and our result is an attempt to approach that.