平面三角剖分图中非连通图的Anti-Ramsey数
The Anti-Ramsey Number of Unconnected Graphs in Plane Triangulation Graphs
DOI: 10.12677/AAM.2023.126304, PDF, HTML, 下载: 130  浏览: 192 
作者: 罗冬连*, 顾俊琪：浙江师范大学数学科学学院，浙江 金华
关键词: 彩虹匹配；Anti-Ramsey数；平面三角剖分；Rainbow Matching； Anti-Ramsey Number； Plane Triangulations
摘要: 给定图 G 的一个边染色，如果图 G 的任意两条边颜色都不相同, 那么就说图 G 是彩虹的。 图 H 在图 G 中的 anti-Ramsey 数是使得边染色图 G 中不存在任何彩虹子图 H 的最大颜色数。 图的 anti-Ramsey 数目前得到广泛的研究, 尤其是匹配在多种图类中的 anti-Ramsey 数得到广泛而 深入的研究。 Gilboa 和Roditty 研究了由小的连通分支构成的图在完全图中的 anti-Ramsey 数，而非连通图在平面图中的 anti-Ramsey 数除匹配外结果较少。 本论文将继续以这个方向研究边染色图中 C3 ∪ tP2 这个非连通图在平面三角剖分图中的 anti-Ramsey 数，得到了对任意n ≥ 2t + 3, t ≥ 2, 2n + 3t − 9 ≤ AR(Tn, C3 ∪ tP2) ≤ 2n + 4t − 5。
Abstract: Given an edge-coloring of a graph G, G is said to be rainbow if any two edges of G receive different colors. Given two graphs G and H, the anti-Ramsey number of H in G is defined to be the maximum number of colors in an edge-colored graph G which contains no rainbow copies of H. The anti-Ramsey numbers for graphs, especially matchings, have been studied in several graph classes. Gilboa and Roditty focused on the anti-Ramsey number of graphs with small components, but the results of the anti-Ramsey number of graphs with small components in plane graph are few. In this paper, we continue the work in this direct and determine the anti-Ramsey number of C3 ∪ tP2 in plane triangulations, then we can get 2n + 3t − 9 ≤ AR(Tn, C3 ∪ tP2) ≤ 2n + 4t − 5 for n ≥ 2t + 3, t ≥ 2.
文章引用：罗冬连, 顾俊琪. 平面三角剖分图中非连通图的Anti-Ramsey数[J]. 应用数学进展, 2023, 12(6): 3030-3038. https://doi.org/10.12677/AAM.2023.126304

参考文献

[1] Erdo˝s, P., Simonovits, M. and Sos, V.T. (1975) Anti-Ramsey Theorems. In: Hajnal, A., Rado, R. and S´os, V.T., Eds., Infinite and Finite Sets II, North-Holland, Amsterdam, 633-643.
[2] Alon, N. (1983) On a Conjecture of Erdo˝s, Simonovits and S´os Concerning anti-Ramsey The- orems. Journal of Graph Theory, 7, 91-94.
https://doi.org/10.1002/jgt.3190070112
[3] Montellano-Ballesteros, J.J. and Neumann-Lara, V. (2005) An Anti-Ramsey Theorem on Cy- cles. Graphs and Combinatorics, 21, 343-354.
https://doi.org/10.1007/s00373-005-0619-y
[4] Simonovits, M. and S´os, V.T. (1984) On Restricting Colorings of Kn. Combinatorica, 4, 101- 110.
https://doi.org/10.1007/BF02579162
[5] Schiermeyer, I. (2004) Rainbow Numbers for Matchings and Complete Graphs. Discrete Math- ematics, 286, 157-162.
https://doi.org/10.1016/j.disc.2003.11.057
[6] Chen, H., Li, X.L. and Tu, J.H. (2009) Complete Solution for the Rainbow Numbers of Match- ings. Discrete Mathematics, 309, 3370-3380.
https://doi.org/10.1016/j.disc.2008.10.002
[7] Haas, R. and Young, M. (2012) The Anti-Ramsey Number of Perfect Matching. Discrete Mathematics, 312, 933-937.
https://doi.org/10.1016/j.disc.2011.10.017
[8] Jiang, T. and West, D.B. (2003) On the Erdo˝s-Simonovits-So´s Conjecture on the Anti-Ramsey Number of a Cycle. Combinatorics, Probability and Computing, 12, 585-598.
https://doi.org/10.1017/S096354830300590X
[9] Jahanbekam, S. and West, D.B. (2016) Anti-Ramsey Problems for t Edge-Disjoint Rainbow Spanning Subgraphs: Cycles, Matchings, or Trees. Journal of Graph Theory, 82, 75-89.
https://doi.org/10.1002/jgt.21888
[10] Jia, Y.X., Lu, M. and Zhang, Y. (2019) Anti-Ramsey Problems in Complete Bipartite Graphs for t Edge-Disjoint Rainbow Spanning Subgraphs: Cycles and Matchings. Graphs and Combi- natorics, 35, 1011-1021.
https://doi.org/10.1007/s00373-019-02053-y
[11] Jin, Z.M. (2017) Anti-Ramsey Numbers for Matchings in 3-Regular Bipartite Graphs. Applied Mathematics and Computation, 292, 114-119.
https://doi.org/10.1016/j.amc.2016.07.037
[12] Jin, Z.M., Ye, K.C., Sun, Y.F. and Chen, H. (2018) Rainbow Matchings in Edge-Colored Complete Split Graphs. European Journal of Combinatorics, 70, 297-316.
https://doi.org/10.1016/j.ejc.2018.01.010
[13] Li, X.L., Tu, J.H. and Jin, Z.M. (2009) Bipartite Rainbow Numbers of Matchings. Discrete Mathematics, 309, 2575-2578.
https://doi.org/10.1016/j.disc.2008.05.011
[14] Li, X.L. and Xu, Z.X. (2009) The Rainbow Number of Matchings in Regular Bipartite Graphs. Applied Mathematics Letters, 22, 1525-1528.
https://doi.org/10.1016/j.aml.2009.03.019
[15] Chen, G., Lan, Y.X. and Song, Z.X. (2019) Planar Anti-Ramsey Numbers of Matchings. Discrete Mathematics, 342, 2106-2111.
https://doi.org/10.1016/j.disc.2019.04.005
[16] Jendrol’, S. (2019) On Rainbow Matchings in Plane Triangulations. Discrete Mathematics, 342, Article 111624.
https://doi.org/10.1016/j.disc.2019.111624
[17] Jendrol’, S., Schiermeyer, I. and Tu, J.H. (2014) Rainbow Numbers for Matchings in Plane Triangulations. Discrete Mathematics, 331, 158-164.
https://doi.org/10.1016/j.disc.2014.05.012
[18] Jin, Z.M., Ma, H.W. and Yu, R. (2022) Rainbow Matchings in an Edge-Colored Planar Bipar- tite Graph. Applied Mathematics and Computation, 432, Article 127356.
https://doi.org/10.1016/j.amc.2022.127356
[19] Jin, Z.M. and Ye, K. (2018) Rainbow Number of Matchings in Planar Graphs. Discrete Math- ematics, 341, 2846-2858.
https://doi.org/10.1016/j.disc.2018.06.044
[20] Pei, Y.F., Lan, Y.X. and He, H. (2022) Improved Bounds for Anti-Ramsey Numbers of Match- ings in Outer-Planar Graphs. Applied Mathematics and Computation, 418, Article 126843.
https://doi.org/10.1016/j.amc.2021.126843
[21] Qin, Z.M., Lan, Y.X. and Shi, Y.T. (2019) Improved Bounds for Rainbow Numbers of Match- ings in Plane Triangulations. Discrete Mathematics, 342, 221-225.
https://doi.org/10.1016/j.disc.2018.09.031
[22] Qin, Z.M., Lan, Y.X., Shi, Y.T. and Yue, J. (2021) Exact Rainbow Numbers for Matchings in Plane Triangulations. Discrete Mathematics, 344, Article 112301.
https://doi.org/10.1016/j.disc.2021.112301
[23] Frankl, P. and Kupavskii, A. (2019) Two Problems on Matchings in Set Families—In the Footsteps of Erdo˝s and Kleitman. Journal of Combinatorial Theory, Series B, 138, 286-313.
https://doi.org/10.1016/j.jctb.2019.02.004
[24] Jin, Z.M. (2021) Anti-Ramsey Number of Matchings in a Hypergraph. Discrete Mathematics, 344, Article 112594.
https://doi.org/10.1016/j.disc.2021.112594
[25] O¨ zkahya, L. and Young, M. (2013) Anti-Ramsey Number of Matchings in Hypergraphs. Dis- crete Mathematics, 313, 2359-2364.
https://doi.org/10.1016/j.disc.2013.06.015
[26] Xue, Y.S., Shan, E.F. and Kang, L.Y. (2022) Anti-Ramsey Number of Matchings in r-Partite r-Uniform Hypergraphs. Discrete Mathematics, 345, Article 112782.
https://doi.org/10.1016/j.disc.2021.112782
[27] Gilboa, S. and Roditty, Y. (2016) Anti-Ramsey Numbers of Graphs with Small Connected Components. Graphs and Combinatorics, 32, 649-662.
https://doi.org/10.1007/s00373-015-1581-y
[28] Bialostocki, A., Gilboa, S. and Roditty, Y. (2015) Anti-Ramsey Numbers of Small Graphs. Ars Combinatoria, 123, 41-53.

为你推荐