Ellingham–Horton graph
Introduction 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'''. 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. The book thickness of the '''Ellingham-Horton 54-graph''' and the '''Ellingham-Horton 78-graph''' is 3 and the queue numbers 2.The first counterexample to the Tutte conjecture was the Horton graph, published by . After the Horton graph, a number of smaller counterexamples to the Tutte conjecture were found. Among them are a 92-vertex graph by , a 78-vertex graph by , and the two Ellingham–Horton graphs.The first Ellingham–Horton graph was published by  and is of order 78.At that time it was the smallest known counterexample to the Tutte conjecture. The second Ellingham–Horton graph was published by  and is of order 54.In 1989, Georges' graph, the smallest currently-known Non-Hamiltonian 3-connected cubic bipartite graph was discovered, containing 50 vertices.
Gallery File:Ellingham-Horton 54-graph 2COL.svg|The chromatic number of the Ellingham–Horton 54-graph is 2.File:Ellingham-Horton 54-graph 3color edge.svg|The chromatic index of the Ellingham–Horton 54-graph is 3.File:Ellingham-Horton 78-graph 2COL.svg|The chromatic number of the Ellingham–Horton 78-graph is 2.File:Ellingham-Horton 78-graph 3color edge.svg|The chromatic index of the Ellingham–Horton 78-graph is 3.
References