Anti-Ramsey numbers for matchings in 3-regular bipartite graphs

作者：Jin, Zemin^*

来源：Applied Mathematics and Computation, 2017, 292: 114-119.

DOI：10.1016/j.amc.2016.07.037

• Anti-Ramsey number
• Rainbow matching
• 3-regular bipartite graph

The anti-Ramsey number AR(K-n, H) was introduced by Erdos, Simonovits and Sos in 1973, which is defined to be the maximum number of colors in an edge coloring of the complete graph K-n without any rainbow H. Later, the anti-Ramsey numbers for several special graph classes in complete are determined. Moreover, researchers generalized the host graph K-n to other graphs, in particular, to complete bipartite graphs and regular bipartite graphs. Li and Xu (2009) [18] proved that: Let G be a k-regular bipartite graph with n vertices in each partite set, then AR(G, mK(2)) = k(m - 2) + 1 for all m >= 2, k >= 3 and n > 3(m - 1). In. this paper, we consider the anti-Ramsey number for matchings in 3-regular bipartite graphs. By using the known result that the vertex cover equals the size of maximum matching in bipartite graphs, we prove that AR(G, mK(2)) = 3 (m - 2) + 1 for n > 3/2 (m - 1) when G is a 3-regular bipartite graph with n vertices in each partite set.

• 出版日期2017-1-1
• 单位浙江师范大学