Rainbow numbers for small graphs in planar graphs. (English) Zbl 1433.05220
Summary: Let \(\mathcal{G}\) be a family of graphs and \(H\) be a subgraph of at least one of the graphs in \(\mathcal{G} \). The rainbow number for \(H\) with respect to \(\mathcal{G}\), denoted \(\operatorname{rb}(\mathcal{G}, H)\), is the minimum number \(k\) such that, if \(H \subseteq G \in \mathcal{G}\), then any \(k\)-edge-coloring of \(G\) contains a rainbow \(H\) (i.e., any two edges of \(H\) are colored distinct). Denote by \(\mathcal{T}_n\) the class of all plane triangulations of order \(n\) and \(W_d\) the wheel graph of order \(d + 1\). In this paper, we determine the exact rainbow numbers for matchings and a triangle with one or two pendant edges with respect to \(W_d\), and the exact rainbow numbers for the triangle with one pendant edge with respect to \(\mathcal{T}_n\). Furthermore, we give upper bounds of rainbow numbers for triangles with two pendant edges with respect to \(\mathcal{T}_n\).
MSC:
| 05C55 | Generalized Ramsey theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05D10 | Ramsey theory |
| 05C15 | Coloring of graphs and hypergraphs |
References:
| [1] | Alon, N., On a conjecture of Erdős, Simonovits and Sós concerning anti-Ramsey theorems, J. Graph Theory, 7, 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] | Bondy, J. A.; Murty, U. S.R., Graph Theory, GTM 244 (2008), Springer · Zbl 1134.05001 |
| [4] | Chen, G.; Lan, Y.; Song, Z.-X., Planar anti-ramsey numbers of matchings, Discr. Math., 342, 2106-2111 (2019) · Zbl 1414.05189 |
| [5] | Chen, H.; Li, X.; Tu, J., Complete solution for the rainbow numbers of matchings, Discr. Math., 309, 3370-3380 (2009) · Zbl 1218.05045 |
| [6] | P. Erdős, M. Simonovits, V.T. Sós, Anti-Ramsey Theorems, Colloquia Mathematica Societatis Ános Bolyai. vol.10, North-Holland, Amsterdam, 1975, PP. 633-643. · Zbl 0316.05111 |
| [7] | P. Frankl, A. Kupavskii, Two problems of P. Erdős on matchings in set families-in the footsteps of Erdős and Kleitman. arXiv:1607.06126, · Zbl 1415.05175 |
| [8] | Fujita, S.; Magnant, C.; Ozeki, K., Rainbow generalizations of Ramsey theory: a survey, Graphs Comb., 26, 1-30 (2010) · Zbl 1231.05178 |
| [9] | Fujita, S.; Kaneko, A.; Schiermeyer, I.; Suzuki, K., A raibow k-matching in the complete graph with r colors, Electron. J. Comb., 16, R51 (2009) · Zbl 1181.05040 |
| [10] | R. Gu, J. Li, Y. Shi, Anti-Ramsey number of paths in hypergraphs, SIAM J. Discrete Math., arXiv: 1901.06092. · Zbl 1431.05145 |
| [11] | Haas, R.; Young, M., The anti-ramsey number of perfect matching, Discr. Math., 312, 933-937 (2012) · Zbl 1241.05031 |
| [12] | 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 |
| [13] | Jendrol’, S.; Schiermeyer, I.; Tu, J., Rainbow numbers for matchings in plane triangulations, Discr. Math., 331, 158-164 (2014) · Zbl 1297.05191 |
| [14] | Jiang, T., Anti-ramsey numbers of subdivided graphs, J. Comb. Theory Ser. B, 85, 361-366 (2002) · Zbl 1019.05047 |
| [15] | Jiang, T.; West, D. B., On the Erdős-Simonovits-Sós conjecture about the anti-Ramsey number of a cycle, Comb. Probab. Comput., 12, 585-598 (2003) · Zbl 1063.05100 |
| [16] | Jin, Z.; Li, X., Anti-ramsey numbers for graphs with independent cycles, Electron. J. Comb., 16, R85 (2009) · Zbl 1186.05052 |
| [17] | Jin, Z.; Wang, F.; Wang, H.; Lv, B., Rainbow triangles in edge-colored Kneser graphs, Appl. Math. Comput., 365, 124724 (2020) · Zbl 1433.05121 |
| [18] | Jin, Z.; Ye, K., Rainbow number of matchings in planar graphs, Discr. Math., 341, 2846-2858 (2018) · Zbl 1393.05116 |
| [19] | Lan, Y.; Shi, Y., Planar turan numbers of short paths, Graphs Comb., 35, 1035-1049 (2019) · Zbl 1426.05070 |
| [20] | Lan, Y.; Shi, Y.; Song, Z.-X., Planar anti-Ramsey numbers for paths and cycles, Discr. Math., 342, 11, 3216-3224 (2019) · Zbl 1419.05138 |
| [21] | Lan, Y.; Shi, Y.; Song, Z.-X., Extremal H-free planar graphs, Electron. J. Comb., 26, 2, 2-11 (2019) · Zbl 1412.05051 |
| [22] | Lan, Y.; Shi, Y.; Song, Z.-X., Extremal theta-free planar graphs, Discr. Math., 342, 12, 111610 (2019) · Zbl 1422.05037 |
| [23] | Lan, Y.; Liu, H.; Qin, Z.; Shi, Y., Degree powers in graphs with a forbidden forest, Discr. Math., 342, 3, 821-835 (2019) · Zbl 1403.05031 |
| [24] | Li, X.; Tu, J.; Jin, Z., Bipartite rainbow numbers of matchings, Discr. Math., 309, 2575-2578 (2009) · Zbl 1179.05088 |
| [25] | L. Lovaśz, M.D. Plummer, Matching Theory, North-Holland, Amsterdam, 1986. · Zbl 0618.05001 |
| [26] | Montellano-Ballesteros, J. J.; Neumann-Lara, V., An anti-Ramsey theorem, Combinatorica, 22, 445-449 (2002) · Zbl 1012.05092 |
| [27] | Özkahya, L.; Young, M., Anti-Ramsey number of matchings in hypergraphs, Discr. Math., 313, 2359-2364 (2013) · Zbl 1281.05111 |
| [28] | Qin, Z.; Lan, Y.; Shi, Y., Improved bounds for rainbow numbers of matchings in plane triangulations, Discr. Math., 342, 221-225 (2019) · Zbl 1400.05089 |
| [29] | Z. Qin, Y. Lan, Y. Shi, J. Yue, Exact rainbow numbers for matchings in plane triangulations. arXiv:1903.00717 · Zbl 1400.05089 |
| [30] | Schiermeyer, I., Rainbow numbers for matchings and complete graphs, Discr. Math., 286, 157-162 (2004) · Zbl 1053.05053 |
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.
