Abstract
Given a graph G, the anti-Ramsey number \(AR(K_n,G)\) is defined to be the maximum number of colors in an edge-coloring of \(K_n\) which does not contain any rainbow G (i.e., all the edges of G have distinct colors). The anti-Ramsey number was introduced by Erdős et al. (Infinite and finite sets, pp 657–665, 1973) and so far it has been determined for several special graph classes. Another related interesting problem posed by Erdős et al. is the uniqueness of the extremal coloring for the anti-Ramsey number. Contrary to the anti-Ramsey number, there are few results about the extremal coloring. In this paper, we show the uniqueness of such extremal coloring for the anti-Ramsey number of matchings in the complete graph.
Similar content being viewed by others
References
Alon N (1983) On a conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems. J Graph Theory 1:91–94
Axenovich M, Jiang T (2004) Anti-Ramsey numbers for small complete bipartite graphs. Ars Comb 73:311–318
Axenovich M, Jiang T, Kündgen A (2004) Bipartite anti-Ramsey numbers of cycles. J Graph Theory 47:9–28
Chen H, Li XL, Tu JH (2009) Complete solution for the rainbow numbers of matchings. Discrete Math 309:3370–3380
Erdős P, Simonovits M, Sós VT (1973) Anti-Ramsey theorems. In: Infinite and finite sets, Keszthely, vol 10 pp 657–665
Fujita S, Magnant C, Ozeki K (2010) Rainbow generalizations of Ramsey theory: a survey. Graphs Comb 26:1–30
Haas R, Young M (2012) The anti-Ramsey number of perfect matching. Discrete Math 312(5):933–937
Gorgol I (2016) Anti-Ramsey numbers in complete split graphs. Discrete Math 339(7):1944–1949
Jendrol S, Schiermeyer I, Tu JH (2014) Rainbow numbers for matchings in plane triangulations. Discrete Math 331(28):158–164
Jiang T (2002) Edge-colorings with no large polychromatic stars. Graphs Comb 18:303–308
Jiang T (2002) Anti-Ramsey numbers of subdivided graphs. J Comb Theory Ser B 85:361–366
Jiang T, West DB (2003) On the Erdős–Simonovits-Sós conjecture on the anti-Ramsey number of a cycle. Comb Probab Comput 12:585–598
Jiang T, West DB (2004) Edge-colorings of complete graphs that avoid polychromatic trees. Discrete Math 274:137–145
Jin ZM (2017) Anti-Ramsey numbers for matchings in 3-regular bipartite graphs. Appl Math Comput 292:114–119
Jin ZM, Li LF (2013) Edge-colorings of complete bipartite graphs without large rainbow trees. Ars Comb 111:75–84
Jin ZM, Li XL (2009) Anti-Ramsey numbers for graphs with independent cycles. Electron J Comb 16(1):R85
Jin ZM, Nweit Oothan, Wang KJ, Wang YL. Anti-Ramsey numbers for matchings in regular bipartite graphs. Discrete Math Alg Appl (to appear)
Jin ZM, Wang YL Bounds for anti-Ramsey number for matchings in regular bipartite graphs. Acta Math Appl Sin Engl Ser (to appear)
Jin ZM, Zang YP (2017) Anti-Ramsey coloring for matchings in complete bipartite graphs. J Comb Optim 33:1–12
Kano M, Li XL (2008) Monochromatic and heterochromatic subgraphs in edge-colored graphs—a survey. Graphs Comb 24:237–263
Li XL, Tu JH, Jin ZM (2009) Bipartite rainbow numbers of matchings. Discrete Math 309:2575–2578
Li XL, Xu ZX (2009) The rainbow number of matchings in regular bipartite graphs. Appl Math Lett 22:1525–1528
Lovász L, Plummer MD (1986) Matching theory. North-Holland, Amsterdam, New York, Oxford, Tokyo
Montellano-Ballesteros JJ, Neumann-Lara V (2002) An anti-Ramsey theorem. Combinatorica 22:445–449
Montellano-Ballesteros JJ, Neumann-Lara V (2005) An anti-Ramsey theorem on cycles. Graphs Comb 21:343–354
Özkahya L, Young M (2013) Anti-Ramsey number of matchings in hypergraphs. Discrete Math 313:2359–2364
Schiermeyer I (2004) Rainbow numbers for matchings and complete graphs. Discrete Math 286:157–162
Simonovits M, Sós VT (1984) On restricting colorings of \(K_n\). Combinatorica 4:101–110
Xu CD, Hu XX, Wang WF, Zhang SG (2016) Rainbow cliques in edge-colored graphs. Eur J Comb 54:193–200
Acknowledgements
This work was supported by National Natural Science Foundation of China (11571320, 11671366 and 11401389) and Zhejiang Provincial Natural Science Foundation (LY14A010009, LY15A010008 and LY17A010017). Sun was partially supported by China Scholarship Council (No.201608330111). The authors are very grateful to the referees for helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Jin, Z., Sun, Y., Yan, S.H.F. et al. Extremal coloring for the anti-Ramsey problem of matchings in complete graphs. J Comb Optim 34, 1012–1028 (2017). https://doi.org/10.1007/s10878-017-0125-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-017-0125-1