Bipartite anti-Ramsey numbers of cycles
Bipartite anti-Ramsey numbers of cycles
复制标题
DOI：
10.1002/jgt.v47:1
复制
发表时间：
2004-09
影响因子：
0.9
通讯作者：
M. Axenovich;T. Jiang;André Kündgen
中科院分区：
文献类型：
--
作者：
M. Axenovich;T. Jiang;André Kündgen
我们确定Km，n的边的着色中的最大颜色数，使得每个长度为2k的循环包含至少两个相同颜色的边。我们的主要工具之一是平衡二部图的广义路覆盖的结果。设g（a，q）是Ka，a的生成子图G中的最大边数，使得覆盖V（G）所需的点不相交偶路和点对的最小数目为q。证明了g（a，q）= a2-aq + max {a，2q-2}.© 2004 Wiley Periodicals，Inc. J Graph Theory 47：928，2004 Tao Jiang的部分研究是在Michigan Technological University，霍顿，MI 49931完成的。
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: 928, 2004 Part of the research of Tao Jiang was done at Michigan Technological University, Houghton, MI 49931.