Bipartite anti‐Ramsey numbers of cycles

We determine the maximum number of colors in a coloring of the edges of K m,n such that every cycle of length 2 k contains at least two edges of the same color. One of our main tools is a result on generalized path covers in balanced bipartite graphs. For positive integers q ≤  a , let g ( a,q ) be the maximum number of edges in a spanning subgraph G of K a,a such that the minimum number of vertex‐disjoint even paths and pairs of vertices from distinct partite sets needed to cover V ( G ) is q . We prove that g (a,q) = a 2  − aq + max { a , 2 q  − 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004