Bull graph

A graph is bull-free if it has no bull as an induced subgraph. The triangle-free graphs are bull-free graphs, since every bull contains a triangle. The strong perfect graph theorem was proven for bull-free graphs long before its proof for general graphs,^[2] and a polynomial time recognition algorithm for Bull-free perfect graphs is known.^[3]

Maria Chudnovsky and Shmuel Safra have studied bull-free graphs more generally, showing that any such graph must have either a large clique or a large independent set (that is, the Erdős–Hajnal conjecture holds for the bull graph),^[4] and developing a general structure theory for these graphs.^[5][6][7]

The chromatic polynomial of the bull graph is ${\displaystyle (x-2)(x-1)^{3}x}$. Two other graphs are chromatically equivalent to the bull graph.

Its characteristic polynomial is ${\displaystyle -x(x^{2}-x-3)(x^{2}+x-1)}$.

Its Tutte polynomial is ${\displaystyle x^{4}+x^{3}+x^{2}y}$.