Английская Википедия:Ellingham–Horton graph
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph.[1] They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte that every cubic 3-connected bipartite graph is Hamiltonian.[2] The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2.[3]
The first counterexample to the Tutte conjecture was the Horton graph, published by Шаблон:Harvtxt.[4] After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by Шаблон:Harvtxt,[5] a 78-vertex graph by Шаблон:Harvtxt,[6] and the two Ellingham–Horton graphs.
The first Ellingham–Horton graph was published by Шаблон:Harvtxt and is of order 78.[7] At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by Шаблон:Harvtxt and is of order 54.[8] In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.[9]
Gallery
-
The chromatic number of the Ellingham–Horton 54-graph is 2.
-
The chromatic index of the Ellingham–Horton 54-graph is 3.
-
The chromatic number of the Ellingham–Horton 78-graph is 2.
-
The chromatic index of the Ellingham–Horton 78-graph is 3.
References
- ↑ Шаблон:MathWorld
- ↑ Шаблон:Citation.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, Universität Tübingen, 2018
- ↑ Шаблон:Citation
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
- ↑ Шаблон:Citation.
