极大外平面图中树的 Anti-Ramsey 数

期刊菜单

极大外平面图中树的 Anti-Ramsey 数
The Anti-Ramsey Number of Trees in Maximal Out-Planar Graph

DOI: 10.12677/AAM.2024.131020, PDF, 下载: 60 浏览: 84
作者: 周韦佳^*, 马华玮：浙江师范大学数学科学学院，浙江金华
关键词: Anti-Ramsey 数；树；极大外平面图；Anti-Ramsey Number； Tree； Maximal Out-Planar Graph

摘要: 对给定的边染色图 G，如果图 G 的每条边颜色都不一样，则称图 G 是彩虹的。Anti-Ramsey 数 AR(K, F ) 是最大的正整数 k，使得图 K 的任意 k-边染色中，图 K 不包含族 F 中任意的彩虹图。近些年来，图的 anti-Ramsey 数吸引了很多图论学者的关注，其中平面图中图的 anti- Ramsey 数得到了深入的研究。Jiang 和 West 研究了 k 条边的树在完全图上的 anti-Ramsey 数，而 k 条边的树在平面图中的 anti-Ramsey 数的结论不多。在本文中，我们研究了 k 条边的树在极大外平面图中的 anti-Ramsey 数，得到了它的上下界。

Abstract: Given a edge-colored graph G, if each edge of G is unique in color, then the graph G is a rainbow graph. The Anti-Ramsey number AR(K, F ) is the largest positive integer k such that in any k-edge-colored graph K, the graph K contains no rainbow graph in the family F . In recent years, the anti-Ramsey number of graph has attracted the attention of many scholars, and the anti-Ramsey numbers for graphs in planar graph has been deeply studied. Jiang and West studied the anti-Ramsey number of trees with k edges in complete graph, while few conclusions were drawn on the anti-Ramsey number of trees with k edges in planar graph. In this paper, we study the anti-Ramsey number of trees with k edges in maximal out-planar graph and get its upper and lower bounds.

文章引用：周韦佳, 马华玮. 极大外平面图中树的 Anti-Ramsey 数[J]. 应用数学进展, 2024, 13(1): 169-175. https://doi.org/10.12677/AAM.2024.131020

参考文献

[1]	Erdős, P., Simonovits, M., and Sós, V.T. (1975) Anti-Ramsey Theorems. In: Hajnal, A., Rado, R. and Sós, V.T., Eds., Inﬁnite and Finite Sets: To Paul Erdős on His 60th Birthday, North-Holland, Amsterdam, 633-643.
[2]	Montellano-Ballesteros, J.J. and Neumann-Lara, V. (2002) An Anti-Ramsey Theorem. Com- binatorica, 22, 445-449. https://doi.org/10.1007/s004930200023
[3]	Simonovits, M. and Sós, V.T. (1984) On Restricting Colorings of Kn. Combinatorica, 4, 101- 110. https://doi.org/10.1007/BF02579162
[4]	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
[5]	Axenovich, M., Jiang, T. and Kündgen, A. (2004) Bipartite Anti-Ramsey Numbers of Cycles. Journal of Graph Theory, 47, 9-28. https://doi.org/10.1002/jgt.20012
[6]	Jiang, T. and West, D.B. (2003) On the Erdős-Simonovits-Sós Conjecture on the Anti-Ramsey Number of a Cycle. Combinatorics, Probability and Computing, 12, 585-598. https://doi.org/10.1017/S096354830300590X
[7]	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
[8]	Alon, N. (1983) On a Conjecture of Erdős Simonovits and Sós Concerning Anti-Ramsey The- orems. Journal of Graph Theory, 7, 91-94. https://doi.org/10.1002/jgt.3190070112
[9]	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
[10]	Xie, T.Y. and Yuan, L.T. (2020) On the Anti-Ramsey Numbers of Linear Forests. Discrete Mathematics, 343, Article 112130. https://doi.org/10.1016/j.disc.2020.112130
[11]	Fang, C.Q., Győri, E., Lu, M. and Xiao, J.M. (2021) On the Anti-Ramsey Number of Forests. Discrete Applied Mathematics, 291, 129-142. https://doi.org/10.1016/j.dam.2020.08.027
[12]	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
[13]	Jin, Z.M. and Zang, Y.P. (2017) Anti-Ramsey Coloring for Matchings in Complete Bipartite Graphs. Journal of Combinatorial Optimization, 33, 1-12.
[14]	Jin, Z.M. and Li, L.F. (2013) Edge-Colorings of Complete Bipartite Graphs without Large Rainbow Trees. Ars Combinatoria, 111, 75-84.
[15]	Jendrol’, S. (2019) On Rainbow Matchings in Plane Triangulations. Discrete Mathematics, 342, Article 111624. https://doi.org/10.1016/j.disc.2019.111624
[16]	Horňák, M., Jendrol’, S., Schiermeyer, I. and Soták, R. (2015) Rainbow Numbers for Cycles in Plane Triangulations. Journal of Graph Theory, 78, 248-257. https://doi.org/10.1002/jgt.21803
[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]	Jiang, T. and West, D.B. (2004) Edge-Colorings of Complete Graphs That Avoid Polychro- matic Trees. Discrete Mathematics, 274, 137-145. https://doi.org/10.1016/j.disc.2003.09.002
[19]	Zhang, M.Q. and Dong, F.M. (2022) Anti-Ramsey Numbers for Trees in Complete Multi- Partite Graphs. Discrete Mathematics, 345, Article 113100. https://doi.org/10.1016/j.disc.2022.113100

为你推荐

友情链接