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

Zemin Jin

Applied Mathematics and Computation, 2017, vol. 292, issue C, 114-119

Abstract: The anti-Ramsey number AR(Kn, H) was introduced by Erdős, Simonovits and Sós in 1973, which is defined to be the maximum number of colors in an edge coloring of the complete graph Kn without any rainbow H. Later, the anti-Ramsey numbers for several special graph classes in complete are determined. Moreover, researchers generalized the host graph Kn 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,mK2)=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,mK2)=3(m−2)+1 for n>32(m−1) when G is a 3-regular bipartite graph with n vertices in each partite set.

Keywords: Anti-Ramsey number; Rainbow matching; 3-regular bipartite graph (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300316304751
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:292:y:2017:i:c:p:114-119

DOI: 10.1016/j.amc.2016.07.037

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().