Compatible spanning circuits in edge-colored graphs

A spanning circuit in a graph is a closed trail (no edge is traversed more than once) visiting (containing) each vertex of the graph. A Hamilton cycle of a graph refers to a spanning circuit that visits each vertex of the graph exactly once, and an Euler tour of a graph refers to a spanning circuit that traverses each edge of the graph. Spanning circuits are common generalizations of Hamilton cycles and Euler tours, two popular and well-studied concepts within graph theory. A compatible spanning circuit in a (not necessarily properly) edge-colored graph is a spanning circuit in which any two consecutively traversed edges have distinct colors.

Sufficient conditions for the existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and Euler tours) in specific edge-colored graphs, and polynomial-time algorithms for finding compatible Euler tours have been considered in previous literature.

In this thesis, we mainly concentrate our efforts on the existence of compatible spanning circuits visiting each vertex exactly (or at least) a specified number of times in specific edge-colored graphs, from both a sufficient condition perspective and an algorithmic perspective. In addition, we also consider similar problems in (di)graphs for which certain generalizations of (arc-) edge-colorings have been defined. In presenting our results, we restate some interesting related problems and conjectures that remain unresolved, as well as we also present several new open problems. We hope that these problems and conjectures attract more attention from other researchers.