The Meredith graph
|Named after||G. H. Meredith|
|Table of graphs and parameters|
The Meredith graph is 4-vertex-connected and 4-edge-connected, has chromatic number 3, chromatic index 5, radius 7, diameter 8, girth 4 and is non-hamiltonian. It has book thickness 3 and queue number 2.
Published in 1973, it provides a counterexample to the Crispin Nash-Williams conjecture that every 4-regular 4-vertex-connected graph is Hamiltonian. However, W. T. Tutte showed that all 4-connected planar graphs are hamiltonian.
The characteristic polynomial of the Meredith graph is .
- Weisstein, Eric W. "Meredith graph". MathWorld.
- Bondy, J. A. and Murty, U. S. R. "Graph Theory". Springer, p. 470, 2007.
- Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- Meredith, G. H. J. "Regular 4-Valent 4-Connected Nonhamiltonian Non-4-Edge-Colorable Graphs." J. Combin. Th. B 14, 55-60, 1973.
- Bondy, J. A. and Murty, U. S. R. "Graph Theory with Applications". New York: North Holland, p. 239, 1976.
- Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969.