Bipartite anti‐Ramsey numbers of cycles |
| |
Authors: | Maria Axenovich Tao Jiang Andr Kündgen |
| |
Institution: | Maria Axenovich,Tao Jiang,André Kündgen |
| |
Abstract: | We determine the maximum number of colors in a coloring of the edges of Km,n such that every cycle of length 2k 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 Ka,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) = a2 ? aq + max {a, 2q ? 2}. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 9–28, 2004 |
| |
Keywords: | bipartite graph anti‐Ramsey problem cycle |
|
|