Bull graph


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

Chromatic and characteristic polynomial

The chromatic polynomial of the bull graph is. Two other graphs are chromatically equivalent to the bull graph.
Its characteristic polynomial is.
Its Tutte polynomial is.