# 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 Template:Harvs.

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 Template:Harvtxt 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,
Template:Harvs 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 Template:Harvnb), 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 Template:Harvs 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 Template:Harvtxt 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 Template:Harvtxt.

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.

## References

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.