Properly colored short cycles in edge-colored graphs. (February 2022)

• Record Type: Journal Article
• Authors: Ding, Laihao; Hu, Jie; Wang, Guanghui; Yang, Donglei
• Is Part Of: European journal of combinatorics. Volume 100(2022)
• Publication Date: 2022-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103436
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 K s, 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) K s, t .