- Bull-free graphs
- Chromatic and characteristic polynomial
- References
| name = Bull graph
| image =
| image_caption = The Bull graph
| namesake =
| vertices = 5
| edges = 5
| automorphisms = 2 (Z/2Z)
| diameter = 3
| girth = 3
| radius = 2
| chromatic_number = 3
| chromatic_index = 3
| properties = Planar
Unit distance
}}
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 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 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 
.
References
2. ^{{citation|last1=Chvátal|first1=V.|author1-link=Václav Chvátal|last2=Sbihi|first2=N.|title=Bull-free Berge graphs are perfect|journal=Graphs and Combinatorics|volume=3|year=1987|pages=127–139|issue=1|doi=10.1007/BF01788536}}.
3. ^{{citation|last1=Reed|first1=B.|author1-link=Bruce Reed (mathematician)|last2=Sbihi|first2=N.|title=Recognizing bull-free perfect graphs|journal=Graphs and Combinatorics|volume=11|year=1995|pages=171–178|issue=2|doi=10.1007/BF01929485}}.
4. ^{{citation|last1=Chudnovsky|first1=M.|author1-link=Maria Chudnovsky|last2=Safra|first2=S.|title=The Erdős–Hajnal conjecture for bull-free graphs|journal=Journal of Combinatorial Theory|series=Series B|volume=98|issue=6|year=2008|pages=1301–1310|doi=10.1016/j.jctb.2008.02.005|url=http://www.columbia.edu/~mc2775/EHbullfree.ps|access-date=2009-06-30|archive-url=https://web.archive.org/web/20100625213302/http://www.columbia.edu/~mc2775/EHbullfree.ps#|archive-date=2010-06-25|dead-url=yes|df=}}.
5. ^{{citation|last=Chudnovsky|first=M.|authorlink=Maria Chudnovsky|year=2008|title=The structure of bull-free graphs. I. Three-edge paths with centers and anticenters|url=http://www.columbia.edu/~mc2775/bulls1.pdf}}.
6. ^{{citation|last=Chudnovsky|first=M.|authorlink=Maria Chudnovsky|year=2008|title=The structure of bull-free graphs. II. Elementary trigraphs|url=http://www.columbia.edu/~mc2775/bulls2.pdf}}.
7. ^{{citation|last=Chudnovsky|first=M.|authorlink=Maria Chudnovsky|year=2008|title=The structure of bull-free graphs. III. Global structure|url=http://www.columbia.edu/~mc2775/bulls3.pdf}}.
- Battle of the Great Wall
- Battle of the Green Fields
- Battle of the Greens
- Battle of the Greens (Panadura)
- Battle of the Guadalquivir (206 BC)
- Battle of the Gulf of Almeria (1591)
- Battle of the Gulf of Almería (1591)
- Battle of the Gulf of Cadiz (1604)
- Battle of the Gulf of Gabes
- Battle of the Gulf of Oman
- Battle of the Halsted Viaduct
- Battle of the Halys
- Battle of the Harpasus
- Battle of the Hawkesbury
- Battle of the Helgoland Bight
- Battle of the Heligoland Bight
- Battle of the Hellespont (321 BC)
- Battle of the Hellespont (321 B.C)
- Battle of the Himera River (446 BC)
- Battle of the Hindus
- Battle of the Hohenzollern Redoubt
- Battle of the Hohenzollern Redoubt (1915)
- Battle of the Hohenzollern Redoubt (1916)
- Battle of the Hotel Nacional of Cuba
- Battle of the House in the Horseshoe