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.[1]
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,[2] 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] [5] [6] [7]
Chromatic and characteristic polynomial
The three graphs with a chromatic polynomial equal to
(
x
−
2
)
(
x
−
1
)
3
x
{\displaystyle (x-2)(x-1)^{3}x}
The chromatic polynomial of the bull graph is
(
x
−
2
)
(
x
−
1
)
3
x
{\displaystyle (x-2)(x-1)^{3}x}
Its characteristic polynomial is
−
x
(
x
2
−
x
−
3
)
(
x
2
+
x
−
1
)
{\displaystyle -x(x^{2}-x-3)(x^{2}+x-1)}
Its Tutte polynomial is
x
4
+
x
3
+
x
2
y
{\displaystyle x^{4}+x^{3}+x^{2}y}
