Compatible spanning circuits in edge-colored graphs
Due to the COVID-19 crisis measures the PhD defence of Zhiwei Guo will take place (partly) online in the presence of an invited audience.
The PhD defence can be followed by a live stream.
Zhiwei Guo is a PhD student in the research group Formal Methods and Tools (FMT). His supervisors are prof.dr.ir. H.J. Broersma from the Faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) and prof.dr. X. Li from the Northwestern Polytechnical University (China).
The research has been carried out within the framework of the MEMORANDUM OF AGREEMENT FOR A DOUBLE DOCTORATE DEGREE BETWEEN NORTHWESTERN POLYTECHNICAL UNIVERSITY, PEOPLE’S REPUBLIC OF CHINA AND THE UNIVERSITY OF TWENTE, THE NETHERLANDS.
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 closed trail containing all vertices of the graph 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.
As presented in this thesis, there are some interesting problems and conjectures that remain unresolved. At the same time, we also present several new open problems. We hope that these problems and conjectures attract more attention from other researchers.
