Premium
Vertex‐disjoint properly edge‐colored cycles in edge‐colored complete graphs
Author(s) -
Li Ruonan,
Broersma Hajo,
Zhang Shenggui
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22536
Subject(s) - combinatorics , mathematics , colored , conjecture , counterexample , disjoint sets , vertex (graph theory) , 1 planar graph , edge coloring , multipartite , discrete mathematics , enhanced data rates for gsm evolution , graph , chordal graph , line graph , computer science , graph power , materials science , physics , quantum mechanics , quantum , quantum entanglement , composite material , telecommunications
It is conjectured that every edge‐colored complete graph G on n vertices satisfyingΔ m o n( G ) ≤ n − 3 k + 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 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.