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"{a}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 and with , every edge-colored graph with no properly colored contains a spanning subgraph which admits an orientation such that every directed cycle in is a properly colored cycle in . Using this result, we show that for , if the Caccetta-H"{a}ggkvist Conjecture holds , then every edge-colored graph of order with minimum color degree at least contains a properly colored cycle of length at most . In addition, we also obtain an asymptotically tight total color degree condition which ensures a properly colored (or rainbow) .

生成讲解博客的中文版本

生成AI智能校验的中文版本