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

¹ Academic Department of Informatics, Federal University of Technology, Paraná, Brazil
² Department of Informatics, Federal University of Paraná, Paraná, Brazil
³ Institute of Computing, Fluminense Federal University, Rio de Janeiro, Brazil
⁴ Alberto Luiz Coimbra Institute for Graduate Studies and Research in Engineering, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

^* Corresponding author: zatesko@utfpr.edu.br

Received: 23 January 2023
Accepted: 13 March 2024

Abstract

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.