Chvátal Graph
Grünbaum conjectured that for every 👁 m>1
, 👁 n>2
, there exists an 👁 m
-regular, 👁 m
-chromatic graph of girth at least
👁 n
. This result is trivial for 👁 n=2
or 👁 m=2,3
, but only a small number of other such graphs are known,
including the 12-node Chvátal graph, 21-node Brinkmann
graph, and 25-node Grünbaum graph. The
Chvátal graph is illustrated above in a number of embeddings (c.f. Bondy;
Knuth 2008, p. 39).
It has 370 distinct (directed) Hamiltonian cycles, giving a unique generalized LCF notation of order 4 (illustrated above), two of order 6 (illustrated above), and 43 of order 1.
The Chvátal graph is implemented in the Wolfram Language as [].
The Chvátal graph is a quartic graph on 12 nodes and 24 edges. It has chromatic number 4,
and girth 4. The Chvátal graph has graph spectrum 👁 (-3)^2(1/2(-1-sqrt(17)))^1(-1)^10^21^4(1/2(-1+sqrt(17)))^14^1
.
See also
Brinkmann Graph, Grünbaum Graphs, Quartic GraphExplore with Wolfram|Alpha
More things to try:
References
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 241, 1976.Grünbaum, B. "A Problem in Graph Coloring." Amer. Math. Monthly 77, 1088-1092, 1970.Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions.. Upper Saddle River, NJ: Addison-Wesley, 2008.Referenced on Wolfram|Alpha
Chvátal GraphCite this as:
Weisstein, Eric W. "Chvátal Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ChvatalGraph.html