Chvátal graph
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970).
| Chvátal graph | |
|---|---|
 | |
| Named after | Václav Chvátal |
| Vertices | 12 |
| Edges | 24 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 4 |
| Automorphisms | 8 (D4) |
| Chromatic number | 4 |
| Chromatic index | 4 |
| Book thickness | 3 |
| Queue number | 2 |
| Properties | Regular Hamiltonian Triangle-free Eulerian |
| Table of graphs and parameters | |
It is triangle-free: its girth (the length of its shortest cycle) is four. It is 4-regular: each vertex has exactly four neighbors. And its chromatic number is 4: it can be colored using four colors, but not using only three. It is, as Chvátal observes, the smallest possible 4-chromatic 4-regular triangle-free graph; the only smaller 4-chromatic triangle-free graph is the Grötzsch graph, which has 11 vertices but has maximum degree 5 and is not regular.
This graph is not vertex-transitive: the automorphisms group has one orbit on vertices of size 8, and one of size 4.
By Brooks’ theorem, every k-regular graph (except for odd cycles and cliques) has chromatic number at most k. It was also known since Erdős (1959) that, for every k and l there exist k-chromatic graphs with girth l. In connection with these two results and several examples including the Chvátal graph, Branko Grünbaum (1970) conjectured that for every k and l there exist k-chromatic k-regular graphs with girth l. The Chvátal graph solves the case k = l = 4 of this conjecture. Grünbaum's conjecture was disproven for sufficiently large k by Johannsen (see Reed 1998), who showed that the chromatic number of a triangle-free graph is O(Δ/log Δ) where Δ is the maximum vertex degree and the O introduces big O notation. However, despite this disproof, it remains of interest to find examples such as the Chvátal graph of high-girth k-chromatic k-regular graphs for small values of k.
An alternative conjecture of Bruce Reed (1998) states that high-degree triangle-free graphs must have significantly smaller chromatic number than their degree, and more generally that a graph with maximum degree Δ and maximum clique size ω must have chromatic number
The case ω = 2 of this conjecture follows, for sufficiently large Δ, from Johanssen's result. The Chvátal graph shows that the rounding up in Reed's conjecture is necessary, because for the Chvátal graph, (Δ + ω + 1)/2 = 7/2, a number that is less than the chromatic number but that becomes equal to the chromatic number when rounded up.
The Chvátal graph is Hamiltonian, and plays a key role in a proof by Fleischner & Sabidussi (2002) that it is NP-complete to determine whether a triangle-free Hamiltonian graph is 3-colorable.
The characteristic polynomial of the Chvátal graph is . The Tutte polynomial of the Chvátal graph has been computed by Björklund et al. (2008).
The independence number of this graph is 4.
Gallery
The chromatic number of the Chvátal graph is 4.
The chromatic index of the Chvátal graph is 4.
The Chvátal graph is Hamiltonian.
Alternative drawing of the Chvátal graph.
References
- Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Computing the Tutte Polynomial in Vertex-Exponential Time", FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA: IEEE Computer Society, pp. 677–686, arXiv:0711.2585, doi:10.1109/FOCS.2008.40, ISBN 978-0-7695-3436-7.
- Chvátal, V. (1970), "The smallest triangle-free 4-chromatic 4-regular graph", Journal of Combinatorial Theory, 9 (1): 93–94, doi:10.1016/S0021-9800(70)80057-6.
- Erdős, Paul (1959), "Graph theory and probability", Canadian Journal of Mathematics, 11: 34–38, doi:10.4153/CJM-1959-003-9.
- Fleischner, Herbert; Sabidussi, Gert (2002), "3-colorability of 4-regular Hamiltonian graphs", Journal of Graph Theory, 42 (2): 125–140, doi:10.1002/jgt.10079.
- Grünbaum, B. (1970), "A problem in graph coloring", American Mathematical Monthly, Mathematical Association of America, 77 (10): 1088–1092, doi:10.2307/2316101, JSTOR 2316101.
- Reed, B. A. (1998), "ω, Δ, and χ", Journal of Graph Theory, 27 (4): 177–212, doi:10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K.