Bull graph

Bull graph
File:Bull graph.circo.svg The bull graph
Vertices	5
Edges	5
Radius	2
Diameter	3
Girth	3
Automorphisms	2 (Z/2Z)
Chromatic number	3
Chromatic index	3
Properties	Planar Unit distance
Table of graphs and parameters

In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges.

It has chromatic number 3, chromatic index 3, radius 2, diameter 3 and girth 3. It is also a self-complementary graph, a block graph, a split graph, an interval graph, a claw-free graph, a 1-vertex-connected graph and a 1-edge-connected graph.

Bull-free graphs

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, and a polynomial time recognition algorithm for Bull-free perfect graphs is known.

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), and developing a general structure theory for these graphs.

Chromatic and characteristic polynomial

File:Chromatically equivalent graphs.svg

The three graphs with a chromatic polynomial equal to $(x-2)(x-1{)}^{3}x$.

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

Its characteristic polynomial is $-x(x^2-x-3)(x^2+x-1)$.

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