Search Results

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.