From Surf Wiki (app.surf) — the open knowledge base
Bull graph
| Field | Value | |
|---|---|---|
| name | Bull graph | |
| image | [[File:Bull graph.circo.svg | 170px]] |
| image_caption | The bull graph | |
| vertices | 5 | |
| edges | 5 | |
| automorphisms | 2 (**Z**/2**Z**) | |
| diameter | 3 | |
| girth | 3 | |
| radius | 2 | |
| chromatic_number | 3 | |
| chromatic_index | 3 | |
| properties | Planar | |
| Unit distance |
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.
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
The chromatic polynomial of the bull graph is (x-2)(x-1)^3x. 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^2y.
References
References
- "Bull Graph".
- (1987). "Bull-free Berge graphs are perfect". [[Graphs and Combinatorics]].
- (1995). "Recognizing bull-free perfect graphs". [[Graphs and Combinatorics]].
- (2008). "The Erdős–Hajnal conjecture for bull-free graphs". [[Journal of Combinatorial Theory]].
- Chudnovsky, M.. (2008). "The structure of bull-free graphs. I. Three-edge paths with centers and anticenters".
- Chudnovsky, M.. (2008). "The structure of bull-free graphs. II. Elementary trigraphs".
- Chudnovsky, M.. (2008). "The structure of bull-free graphs. III. Global structure".
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Bull graph — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report