Chvátal graph
| 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 |
| Properties |
Regular Hamiltonian Triangle-free Eulerian |
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).
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.