Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs

2017/08/29 by Li, Ruonan, Broersma, Hajo, Zhang, Shenggui
#05C15 #05C20 #05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1708.08641

Abstract

It is conjectured that every edge-colored complete graph G on n vertices satisfying Δ^mon(G)≤ n-3k+1 contains k vertex-disjoint properly edge-colored cycles. We confirm this conjecture for k=2, prove several additional weaker results for general k, 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 multi-partite 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.

Related

• Properly colored cycles in edge-colored complete graphs containing no monochromatic triangles: a vertex-pancyclic analogous result
• Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Note on edge-colored graphs and digraphs without properly colored cycles
• Note on Disjoint Cycles in Multipartite Tournaments