Properly colored subgraphs in edge-colored graphs
Tingtin Han is a PhD student in the department Formal Methods and Tools. (Co)Promotors are prof.dr.ir. H.J. Broersma from the faculty of Electrical Engineering, Mathematics and Computer Science, and prof.dr. S. Zhang from the Northwestern Polytechnical University, China.
This thesis contains a number of new contributions on properly colored subgraphs (PC subgraphs for short) in edge-colored graphs. These new results involve the existence of short PC cycles, (vertex-disjoint) PC cycles of different lengths, PC cycle-factors and PC vertex-pancyclicity.
It is well-known that a graph is bipartite graph if and only if it contains no odd cycles, and checking whether a graph on vertices and edges is bipartite can be done in time . One natural problem in the research of edge-colored graphs is to characterize the coloring of edge-colored complete graphs containing no PC odd cycles. Based on a well-known Gallai partition theorem, in Chapter 2 we obtain a complete characterization of edge-colored complete graphs containing no PC odd cycles, and we give an effective algorithm with complexity for deciding the existence of PC odd cycles. This is quite different from the result in uncolored graphs. It is interesting to note that analogous problems in edge-colored graphs appear to be more difficult than in uncolored graphs, even for edge-colored complete graphs.
Another natural problem in the research of edge-colored graphs is the existence of short PC cycles in edge-colored graphs. A well-known conjecture by Caccetta and Häggkvist states that every digraph on vertices with minimum outdegree at least has a directed cycle of length at most . Motivated by minimum color degree and maximum monochromatic degree conditions for the existence of short cycles in edge-colored complete graphs, in Chapter 3 we give a maximum monochromatic degree condition for the existence of PC 4-cycles and characterize the extremal graphs for several known results on the existence of PC triangles. Edge number conditions and degree conditions for the existence of triangles and 4-cycle in graphs are not hard to obtain. However, the theorems and proofs involving minimum color degree conditions and maximum monochromatic degree conditions for PC triangles or PC 4-cycles in edge-colored complete graphs are far from trivial.
It is widely known that every graph with minimum degree at least contains cycles of different lengths. Analogously, every digraph with minimum out-degree at least contains directed cycles of different lengths. For any positive integer , Wang and Li constructed an edge-colored graph with that contains no PC cycles. It is a natural approach to consider the existence of PC cycles of different lengths in edge-colored complete graphs. In Chapter 4, we give sufficient conditions for the existence of (vertex-disjoint) PC cycles of different lengths, which are far from trivial.
A classical theorem of Dirac states that every graph on vertices with minimum degree contains a Hamilton cycle. However, as a natural analogy of Dirac's Theorem, the problem of giving a sufficient color degree condition for the existence of PC Hamilton cycles in edge-colored graphs is more difficult. Lo gave an asymptotically sharp solution and gave a sharp color degree condition for the existence of a PC cycle-factor in an edge-colored graph. In Chapter 5, we give a sufficient color degree condition for the existence of PC cycle-factors in edge-colored balanced bipartite graphs.
Moon established that if a tournament has a Hamilton cycle, then it is vertex-pancyclic. Häggkvist and Manoussakis established that if a bipartite tournament has a Hamilton cycle, then it is even vertex-pancyclic, unless it belongs to a special class of digraphs. R. Li showed that an edge-colored complete graph containing no monochromatic triangles is PC vertex-pancyclic unless it belongs to two special classes of edge-colored graphs. In Chapter 6, we show that if an edge-colored balanced complete bipartite graphs contains no monochromatic paths of length three and it has a PC Hamilton cycle, then it is PC even vertex-pancyclic, unless it belongs to two special classes of edge-colored complete graphs. Note that the analogous problems in edge-colored complete (bipartite) graphs appears to be more difficult than in (bipartite) tournaments, even after we add forbidden subgraph conditions.
Throughout this thesis, we have investigated the existence of PC subgraphs under different types of conditions, such as color degree conditions, monochromatic degree conditions and total color degree conditions. Although we have made some comparisons on the problems of different types of PC cycles between directed graphs and edge-colored graphs, there are still many interesting problems and conjectures that remain open. We hope that this will attract more attentions from many researchers.
