Rainbow number of matchings in planar graphs. (English) Zbl 1393.05116
Summary: The rainbow number \(\operatorname{rb}(G, H)\) for the graph \(H\) in \(G\) is defined to be the minimum integer \(c\) such that any \(c\)-edge-coloring of \(G\) contains a rainbow \(H\). As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. S. Jendrol’ et al. [ibid. 331, 158–164 (2014; Zbl 1297.05191)] initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching \(kK_2\) in the plane triangulations, where the gap between the lower and upper bounds is \(O(k^3)\). In this paper, we show that the rainbow number of the matching \(kK_2\) in maximal outerplanar graphs of order \(n\) is \(n + O(k)\). Using this technique, we show that the rainbow number of the matching \(kK_2\) in some subfamilies of plane triangulations of order \(n\) is \(2 n + O(k)\). The gaps between our lower and upper bounds are only \(O(k)\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
Citations:
Zbl 1297.05191References:
| [1] | Alon, N., On a conjecture of Erdős, simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory, 1, 91-94, (1983) · Zbl 0456.05038 |
| [2] | Axenovich, M.; Jiang, T.; Kündgen, A., Bipartite anti-Ramsey numbers of cycles, J. Graph Theory, 47, 9-28, (2004) · Zbl 1062.05095 |
| [3] | Chen, H.; Li, X. L.; Tu, J. H., Complete solution for the rainbow numbers of matchings, Discrete Math., 309, 3370-3380, (2009) · Zbl 1218.05045 |
| [4] | Erdős, P.; Simonovits, M.; Sós, V. T., Anti-Ramsey theorems, (Colloq. Math. Soc. Janos Bolyai, Infinite and Finite Sets, vol. 10, (1973), Keszthely Hungary), 657-665 |
| [5] | Fujita, S.; Magnant, C.; Ozeki, K., Rainbow generalizations of Ramsey theory: A survey, Graphs Combin., 26, 1-30, (2010) · Zbl 1231.05178 |
| [6] | Fujita, S.; Magnant, C.; Ozeki, K., Rainbow generalizations of Ramsey theory - A dynamic survey, Theory Appl. Graphs, 0, 1, (2014) |
| [7] | Horňák, M.; Jendrol, S.; Schiermeyer, I.; Soták, R., Rainbow numbers for cycles in plane triangulations, J. Graph Theory, 78, 248-257, (2015) · Zbl 1309.05107 |
| [8] | Jendrol, S.; Schiermeyer, I.; Tu, J. H., Rainbow numbers for matchings in plane triangulations, Discrete Math., 331, 28, 158-164, (2014) · Zbl 1297.05191 |
| [9] | Jiang, T.; West, D. B., On the Erdős-simonovits-Sós conjecture on the anti-Ramsey number of a cycle, Combin. Probab. Comput., 12, 585-598, (2003) · Zbl 1063.05100 |
| [10] | Jin, Z. M., Anti-Ramsey numbers for matchings in 3-regular bipartite graphs, Appl. Math. Comput., 292, 114-119, (2017) · Zbl 1410.05147 |
| [11] | Jin, Z. M.; Nweit, Oothan; Wang, K. J.; Wang, Y. L., Anti-Ramsey numbers for matchings in regular bipartite graphs, Discrete Math. Algorithms Appl., 9, 2, 1750019, (2017), 7 pp. · Zbl 1362.05048 |
| [12] | Jin, Z. M.; Sun, Y. F.; Yan, Sherry H. F.; Zang, Y. P., Extremal coloring for the anti-Ramsey problem of matchings in complete graphs, J. Comb. Optim., 34, 1012-1028, (2017) · Zbl 1374.05090 |
| [13] | Jin, Z. M.; Ye, K. C.; Sun, Y. F.; Chen, H., Rainbow matchings in edge-colored complete split graphs, European J. Combin., 70, 297-316, (2018) · Zbl 1384.05088 |
| [14] | Jin, Z. M.; Zang, Y. P., Anti-Ramsey coloring for matchings in complete bipartite graphs, J. Comb. Optim., 33, 1-12, (2017) · Zbl 1357.05044 |
| [15] | Kano, M.; Li, X. L., Monochromatic and heterochromatic subgraphs in edge-colored graphs - a survey, Graphs Combin., 24, 237-263, (2008) · Zbl 1190.05045 |
| [16] | Y.X. Lan, Y.T. Shi, Z.X. Song, Planar anti-Ramsey numbers for paths and cycles, arXiv:1709.00970; Y.X. Lan, Y.T. Shi, Z.X. Song, Planar anti-Ramsey numbers for paths and cycles, arXiv:1709.00970 |
| [17] | Li, X. L.; Tu, J. H.; Jin, Z. M., Bipartite rainbow numbers of matchings, Discrete Math., 309, 2575-2578, (2009) · Zbl 1179.05088 |
| [18] | Li, X. L.; Xu, Z. X., The rainbow number of matchings in regular bipartite graphs, Appl. Math. Lett., 22, 1525-1528, (2009) · Zbl 1171.05394 |
| [19] | Lovász, L.; Plummer, M. D., Matching theory, (1986), North-Holland Amsterdam, New York, Oxford, Tokyo · Zbl 0618.05001 |
| [20] | Montellano-Ballesteros, J. J.; Neumann-Lara, V., An anti-Ramsey theorem, Combinatorica, 22, 445-449, (2002) · Zbl 1012.05092 |
| [21] | Montellano-Ballesteros, J. J.; Neumann-Lara, V., An anti-Ramsey theorem on cycles, Graphs Combin., 21, 343-354, (2005) · Zbl 1075.05058 |
| [22] | Özkahya, L.; Young, M., Anti-Ramsey number of matchings in hypergraphs, Discrete Math., 313, 2359-2364, (2013) · Zbl 1281.05111 |
| [23] | Schiermeyer, I., Rainbow numbers for matchings and complete graphs, Discrete Math., 286, 157-162, (2004) · Zbl 1053.05053 |
| [24] | Simonovits, M.; Sós, V. T., On restricting colorings of \(K_n\), Combinatorica, 4, 101-110, (1984) · Zbl 0538.05047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
