Bull-free graphs and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>χ</mml:mi> </mml:math> -boundedness

Abstract

<jats:p> A <jats:italic>bull</jats:italic> is a graph obtained from a four-vertex path by adding a vertex adjacent to the two middle vertices of the path. A graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> is <jats:italic>bull-free</jats:italic> if no induced subgraph of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> is a bull. We prove that for all <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>ℕ</mml:mi> </mml:mrow> </mml:math> , if <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> is a bull-free graph of clique number at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> </mml:math> and every triangle-free induced subgraph of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> has chromatic number at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>t</mml:mi> </mml:math> , then <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> has chromatic number at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo form="prefix">log</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> . We further show that the bound <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mo form="prefix">log</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> is best possible up to a multiplicative constant in the exponent. </jats:p> <jats:p> Thomassé, Trotignon, and Vušković (2017) were the first to give a bound of the form <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo form="prefix">log</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> </mml:msup> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , with a proof that uses Chudnovsky’s structure theorem for bull-free graphs. This was improved by Chudnovsky, Cook, Davies, and Oum (2026) to a bound of the form <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>k</mml:mi> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msup> </mml:math> , with a 10-page proof that again relies heavily on Chudnovsky’s structure theorem. </jats:p> <jats:p>Our proof is a single page long and completely avoids the structure theorem, instead using only a result of Chudnovsky and Safra (which itself has a short proof).</jats:p>