|
|
极大外平面图中树的 Anti-Ramsey 数
|
Abstract:
对给定的边染色图 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 数，得到了它的上下界。
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.
| [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 |
