Bull graph

Bull graph
	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.[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] 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]

Chromatic and characteristic polynomial

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$ .

References

Weisstein, Eric W. "Bull Graph". MathWorld.
Chvátal, V.; Sbihi, N. (1987), "Bull-free Berge graphs are perfect", Graphs and Combinatorics, 3 (1): 127–139, doi:10.1007/BF01788536.
Reed, B.; Sbihi, N. (1995), "Recognizing bull-free perfect graphs", Graphs and Combinatorics, 11 (2): 171–178, doi:10.1007/BF01929485.
Chudnovsky, M.; Safra, S. (2008), "The Erdős–Hajnal conjecture for bull-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1301–1310, doi:10.1016/j.jctb.2008.02.005, archived from the original on 2010-06-25, retrieved 2009-06-30.
Chudnovsky, M. (2008), The structure of bull-free graphs. I. Three-edge paths with centers and anticenters (PDF).
Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs (PDF).
Chudnovsky, M. (2008), The structure of bull-free graphs. III. Global structure (PDF).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Weisstein, Eric W. "Bull Graph". MathWorld.

[2] Chvátal, V.; Sbihi, N. (1987), "Bull-free Berge graphs are perfect", Graphs and Combinatorics, 3 (1): 127–139, doi:10.1007/BF01788536.

[3] Reed, B.; Sbihi, N. (1995), "Recognizing bull-free perfect graphs", Graphs and Combinatorics, 11 (2): 171–178, doi:10.1007/BF01929485.

[4] Chudnovsky, M.; Safra, S. (2008), "The Erdős–Hajnal conjecture for bull-free graphs", Journal of Combinatorial Theory, Series B, 98 (6): 1301–1310, doi:10.1016/j.jctb.2008.02.005, archived from the original on 2010-06-25, retrieved 2009-06-30.

[5] Chudnovsky, M. (2008), The structure of bull-free graphs. I. Three-edge paths with centers and anticenters (PDF).

[6] Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs (PDF).

[7] Chudnovsky, M. (2008), The structure of bull-free graphs. III. Global structure (PDF).