There are no Cubic Graphs on 26 Vertices with Crossing Number 11

Michael Haythorpe, Alex Newcombe

Published 2018-04-27Version 1

We show that no cubic graphs of order 26 have crossing number 11, which proves a conjecture of Ed Pegg Jr and Geoffrey Exoo that the smallest cubic graphs with crossing number 11 have 28 vertices. This result is achieved by first eliminating all girth 3 graphs from consideration, and then using the recently developed QuickCross heuristic to find good embeddings of each remaining graph. In the cases where the embedding found has 11 or more crossings, the heuristic is re-run with a different settings of parameters until an embedding with fewer than 11 crossings is found; this is required in less than 3% of the graphs.