2026-08-22T20:40:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27426 2026-08-21T14:42:39Z ddc:004 open_access

Generalized Snarks, Disjoint Perfect Matchings, and Graph Covers Filipi, Filip Kratochvíl, Jan Nedela, Roman graph graph cover perfect matching NP-completeness We explore the interplay among three classical notions in graph theory: edge-colorings, perfect matchings, and graph coverings (locally bijective homomorphisms of graphs). In this paper, we consider undirected graphs in full generality of this notion: in contrast to the standard notion of a simple graph, our graphs may contain loops, semi-edges, and multiple edges. Many well-studied graph concepts, including matchings, edge-colorings, and covering projections, extend naturally to such graphs. Nevertheless, the role of simple graphs for graph covering problems is central, as emphasized in [J. Bok, J. Fiala, N. Jedličková, J. Kratochvíl, and M. Seifrtová. Computational complexity of covering disconnected multigraphs. Discret. Appl. Math., 359:229–243, 2024]. In that work, a relation "being stronger" was defined (a graph A is stronger than a graph B if every simple graph that covers A also covers B), and it was conjectured that if A has no semi-edges, then A is stronger than B if and only if A covers B. In their extended abstract presented at Eurocomb'23, Kratochvíl and Nedela proved this conjecture for 3-regular 1-vertex graphs B (and arbitrary A). They also introduced the notion (A,B)-snark for a simple graph G that demonstrates that A is not stronger than B. We continue this line of research in the current paper. As the main result, we show that for every graph A, there exists a simple graph D that covers A in such a way that the maximum number of pairwise disjoint perfect matchings equals the maximum number of pairwise disjoint perfect semi-matchings in A, i.e., spanning 1-regular subgraphs. Notably, the proof is constructive. As a corollary, we obtain a necessary condition for A to be stronger than B in general. This condition turns out to be sufficient whenever B is a 1-vertex graph (there are infinitely many of them), which, in particular, proves the aforementioned conjecture of Bok et al. in this case. Finally, we provide a constructive alternative to the existential NP-hardness proof of covering disconnected graphs in Bok et al. for the case when the target graph contains a 1-vertex component which itself determines an NP-hard covering problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Filip Filipi and Jan Kratochvíl and Roman Nedela 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.45 urn:nbn:de:0030-drops-274265 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.45 eng https://creativecommons.org/licenses/by/4.0/legalcode