It is conjectured that every edge‐colored complete graph <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> on <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> vertices satisfying <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> contains <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> vertex‐disjoint properly edge‐colored cycles. We confirm this conjecture for <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> , prove several additional weaker results for general <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> , and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge‐colored cycles in edge‐colored complete graphs and directed cycles in multipartite tournaments. Using this relationship and our results on edge‐colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.
With respect to specific cycle-related problems, edge-colored graphs can be considered as a generalization of directed graphs. We show that properly edge-colored theta graphs play a key role in characterizing the difference between edge-colored complete graphs and multipartite tournaments. We also establish sufficient conditions for an edge-colored complete graph to contain a small and a large properly edge-colored theta graph, respectively.
1 March 2019 in Combinatorics, Probability and Computing
For an edge-coloured graph G, the minimum colour degree of G means the minimum number of colours on edges which are incident to each vertex of G. We prove that if G is an edge-coloured graph with minimum colour degree at least 5, then V(G) can be partitioned into two parts such that each part induces a subgraph with minimum colour degree at least 2. We show this theorem by proving amuch stronger form. Moreover, we point out an important relationship between our theorem and Bermond and Thomassen’s conjecture in digraphs.