Premium
Bipartite anti‐Ramsey numbers of cycles
Author(s) -
Axenovich Maria,
Jiang Tao,
Kündgen André
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20012
Subject(s) - combinatorics , mathematics , bipartite graph , disjoint sets , vertex (graph theory) , graph , discrete mathematics , complete bipartite graph , path (computing) , computer science , programming language
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