Chvátal graph

Chvátal graph
Eulerian
Table of graphs and parameters

In the

.

Coloring, degree, and girth

The Chvátal graph is

By

Brooks’ theorem

, every ${\displaystyle k}$-regular graph (except for odd cycles and cliques) has chromatic number at most ${\displaystyle k}$. It was also known since Erdős (1959) that, for every ${\displaystyle k\geq 3}$ and ${\displaystyle \ell \geq 3}$ there exist ${\displaystyle k}$-chromatic graphs with girth ${\displaystyle \ell }$.^[2] In connection with these two results and several examples including the Chvátal graph, Branko Grünbaum conjectured that for every ${\displaystyle k}$ and ${\displaystyle \ell }$ there exist ${\displaystyle k}$-chromatic ${\displaystyle k}$-regular graphs with girth ${\displaystyle \ell }$.^[3] The Chvátal graph solves the case ${\displaystyle k=\ell =4}$ of this conjecture.^[1] Grünbaum's conjecture was disproven for sufficiently large ${\displaystyle k}$ by Johannsen, who showed that the chromatic number of a triangle-free graph is ${\displaystyle O(\Delta /\log \Delta )}$ where ${\displaystyle \Delta }$ is the maximum vertex degree and the ${\displaystyle O}$ introduces big O notation.^[4] However, despite this disproof, it remains of interest to find examples such as the Chvátal graph of high-girth ${\displaystyle k}$-chromatic ${\displaystyle k}$-regular graphs for small values of ${\displaystyle k}$.

An alternative conjecture of Bruce Reed 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 ${\displaystyle \Delta }$ and

size ${\displaystyle \omega }$ must have chromatic number^[4] The case ${\displaystyle \omega =2}$ of this conjecture follows, for sufficiently large ${\displaystyle \Delta }$, 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, ${\displaystyle (\Delta +\omega +1)/2=7/2}$, a number that is less than the chromatic number but that becomes equal to the chromatic number when rounded up.

Other properties

This graph is not vertex-transitive: its automorphism group has one orbit on vertices of size 8, and one of size 4.

The Chvátal graph is

The characteristic polynomial of the Chvátal graph is ${\displaystyle (x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)}$. The Tutte polynomial of the Chvátal graph has been computed by Björklund et al. (2008).^[6]

The

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

External links

• Weisstein, Eric W., "Chvátal Graph", MathWorld