The hardness of recognising poorly matchable graphs and the hunting of the d-snark

An r -graph is an r -regular graph G on an even number of vertices where every odd set X ⊆ V ( G ) is connected by at least r edges to its complement V ( G ) \ X . Every r -graph has a perfect matching and in a poorly matchable r -graph every pair of perfect matchings intersect, which implies that poorly matchable r -graphs are not r -edge-colourable. We prove, for each fixed r ≥ 3, that poorly matchable r -graph recognition is coNP-complete, an indication that, for each odd d ≥ 3, it may be a hard problem to recognise d -regular ( d − 1)-edge-connected non- d -edge-colourable graphs, referred to as d -snarks in this paper. We show how to construct, for every fixed odd d ≥ 5, an infinite family of d -snarks. These families provide a natural extension to the well-known Loupekine snarks. We also discuss how the hunting of the smallest d -snarks may help in strengthening and better understanding the major Overfull Conjecture on edge-colouring simple graphs.