Properly Colored Cycles in Edge‐Colored Balanced Bipartite Graphs

Let (Formula presented.) denote a (not necessarily properly) edge-colored balanced bipartite graph on (Formula presented.) vertices, that is, in which every edge is assigned a color. A cycle (Formula presented.) in (Formula presented.) is called properly colored if any two consecutive edges of (Formula presented.) have distinct colors. A properly colored cycle-factor of (Formula presented.) is a spanning subgraph each component of which is a properly colored cycle. We say that (Formula presented.) is properly colored even vertex-pancyclic if every vertex of (Formula presented.) is contained in properly colored cycles of all possible even lengths. Let (Formula presented.) denote the minimum number of distinct colors appearing on the edges incident with a vertex of (Formula presented.). In our first main result we show that (Formula presented.) implies (Formula presented.) contains a properly colored cycle of length at most 6. This result can be seen as a specific case regarding the colored version of the Caccetta-Häggkvist Conjecture for directed graphs and its recently studied bipartite version by Seymour and Spirkl in [Combinatorica 4 (2020) 575–599]. In our second main result we show that (Formula presented.) implies that (Formula presented.) contains a properly colored cycle-factor. We also show that the color degree bound is essentially sharp. Our final result is the following generalization of a result of Häggkvist and Manoussakis on bipartite tournaments in [Combinatorica 9 (1989) 33–38]. If (Formula presented.) is a complete bipartite graph containing no monochromatic paths of length three and (Formula presented.) has a properly colored Hamilton cycle, then (Formula presented.) is properly colored even vertex-pancyclic, unless (Formula presented.) belongs to two special classes of edge-colored graphs.