2019/11/05 by Laihao Ding, Ding, Laihao, Jie Hu +5
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1911.01555
openalex publication_date 2019/11/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Properly colored cycles in edge-colored graphs are closely related to directed cycles in oriented graphs. As an analogy of the well-known Caccetta-Häggkvist Conjecture, we study the existence of properly colored cycles of bounded length in an edge-colored graph. We first prove that for all integers s and t with t≥ s≥2, every edge-colored graph G with no properly colored Ks,t contains a spanning subgraph H which admits an orientation D such that every directed cycle in D is a properly colored cycle in G. Using this result, we show that for r≥4, if the Caccetta-Häggkvist Conjecture holds , then every edge-colored graph of order n with minimum color degree at least n/r+2√(n)+1 contains a properly colored cycle of length at most r. In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) Ks,t.