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.

A strong snark is a 2-connected cubic graph which is not 3-edge-colourable and remains so after deleting any edge and suppressing the resulting 2-valent vertices. Strong snarks were introduced by Jaeger in 1985 as a class of cubic graphs that might include counterexamples to the cycle double cover conjecture, the 5-flow conjecture, or to other related longstanding conjectures. With these conjectures still widely open, strong snarks merit further investigation. In this paper we study colouring defect of strong snarks, an invariant introduced by Steffen in 2015 as the minimum number of edges of a cubic graph left uncovered by any set of three perfect matchings. This invariant provides one of measures of edge uncolourability of cubic graphs recently studied by several authors. Our main result shows that the colouring defect of a strong snark is at least 6, and that the bound is sharp.

A longstanding conjecture of Alon and Tarsi, and independly Jaeger (1985), suggests that the edges of every bridgeless graph can be covered with cycles of total length at most 7/5 • m , where m is the number of edges. We study the relationship between cycle covers and structural properties of cubic graphs, focusing on their colouring defect. This invariant, introduced by Steffen in 2015, is defined as the minimum number of edges left uncovered by any set of three perfect matchings of a cubic graph. We show that every bridgeless cubic graph with colouring defect not exceeding 3 admits a cycle cover of length at most 4/3 • m + 1, just one step above the universal lower bound of 4/3 • m for all cubic graphs. We also prove that, regardless of defect, the same bound holds for bridgeless cubic graphs that have an edge whose endvertices removed yield a 3-edge-colourable graph and the edge lies on a 5-cycle. Motivated by our investigations, we introduce a new invariant for cubic graphs, their covering excess, to measure the deviation of the length of a shortest cycle cover from the mentioned lower bound. Finally, we show that every bridgeless cubic graph with covering excess at most 1 admits a cycle double cover.

A map is a \(2\) -cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices, which preserves the vertex-edge-face incidences in the embedding. Every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no “truly subquadratic” algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map on an orientable surface of genus \(g\neq 0\) , parametrized by the genus \(g\) . A map on an orientable surface is uniform if the cyclic vector of sizes of faces incident to a vertex \(v\) does not depend on the choice of \(v\) . The algorithm applies a sequence of local reductions and produces a uniform map while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the associated uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover. The algorithm can be used to solve the map isomorphism problem between maps (orientable or non-orientable) of bounded negative Euler characteristic.

A map is a 2-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. An automorphism of a map can be thought of as a permutation of the vertices which preserves the vertex-edge-face incidences in the embedding. When the underlying surface is orientable, every automorphism of a map determines an angle-preserving homeomorphism of the surface. While it is conjectured that there is no "truly subquadratic" algorithm for testing map isomorphism for unconstrained genus, we present a linear-time algorithm for computing the generators of the automorphism group of a map, parametrized by the genus of the underlying surface. The algorithm applies a sequence of local reductions and produces a uniform map, while preserving the automorphism group. The automorphism group of the original map can be reconstructed from the automorphism group of the uniform map in linear time. We also extend the algorithm to non-orientable surfaces by making use of the antipodal double-cover.