Planar anti-Ramsey numbers of matchings

被引:15
作者
Chen, Gang [1 ]
Lan, Yongxin [2 ,3 ]
Song, Zi-Xia [4 ]
机构
[1] Ningxia Univ, Sch Math & Stat, Yinchuan, Peoples R China
[2] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
[3] Nankai Univ, LPMC, Tianjin 300071, Peoples R China
[4] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA
关键词
Rainbow subgraph; Anti-Ramsey number; Planar anti-Ramsey number; RAINBOW NUMBERS;
D O I
10.1016/j.disc.2019.04.005
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a positive integer n and a planar graph H, let T-n(H) be the family of all plane triangulations T on n vertices such that T contains a subgraph isomorphic to H. The planar anti-Ramsey number of H, denoted ar(p)(n, H), is the maximum number of colors in an edge-coloring of a plane triangulation T is an element of T-n(H) such that T contains no rainbow copy of H. In this paper we study planar anti-Ramsey numbers of matchings. For all t >= 1, let M-t denote a matching of size t. We prove that for all t >= 6 and n >= 3t - 6, 2n + 3t - 15 <= ar(p)(n, M-t) <= 2n + 4t - 14, which significantly improves the existing lower and upper bounds for ar(p)(n, M-t). It seems that for each t >= 6, the lower bound we obtained is the exact value of ar(p)(n, M-t) for sufficiently large n. This is indeed the case for M-6. We prove that ar(p)(n, M-6) = 2n + 3 for all n >= 30. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:2106 / 2111
页数:6
相关论文
共 50 条
[21]   Complexity of computing the anti-Ramsey numbers for paths [J].
Amiri, Saeed Akhoondian ;
Popa, Alexandru ;
Roghani, Mohammad ;
Shahkarami, Golnoosh ;
Soltani, Reza ;
Vahidi, Hossein .
THEORETICAL COMPUTER SCIENCE, 2025, 1044
[22]   Extremal coloring for the anti-Ramsey problem of matchings in complete graphs [J].
Zemin Jin ;
Yuefang Sun ;
Sherry H. F. Yan ;
Yuping Zang .
Journal of Combinatorial Optimization, 2017, 34 :1012-1028
[23]   Anti-Ramsey Numbers of Doubly Edge-Critical Graphs [J].
Jiang, Tao ;
Pikhurko, Oleg .
JOURNAL OF GRAPH THEORY, 2009, 61 (03) :210-218
[24]   Anti-Ramsey numbers for cycles in the generalized Petersen graphs [J].
Liu, Huiqing ;
Lu, Mei ;
Zhang, Shunzhe .
APPLIED MATHEMATICS AND COMPUTATION, 2022, 430
[25]   Anti-Ramsey number of matchings in r-partite r-uniform hypergraphs [J].
Xue, Yisai ;
Shan, Erfang ;
Kang, Liying .
DISCRETE MATHEMATICS, 2022, 345 (04)
[26]   Anti-Ramsey Numbers in Complete k-Partite Graphs [J].
Ding, Jili ;
Bian, Hong ;
Yu, Haizheng .
MATHEMATICAL PROBLEMS IN ENGINEERING, 2020, 2020
[27]   Anti-Ramsey Numbers of Loose Paths and Cycles in Uniform Hypergraphs [J].
Li, Tong ;
Tang, Yucong ;
Wang, Guanghui ;
Yan, Guiying .
GRAPHS AND COMBINATORICS, 2025, 41 (04)
[28]   ANTI-RAMSEY NUMBER OF HANOI GRAPHS [J].
Gorgol, Izolda ;
Lechowska, Anna .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) :285-296
[29]   Anti-Ramsey numbers for trees in complete multi-partite graphs [J].
Zhang, Meiqiao ;
Dong, Fengming .
DISCRETE MATHEMATICS, 2022, 345 (12)
[30]   On the anti-Ramsey number of forests [J].
Fang, Chunqiu ;
Gyori, Ervin ;
Lu, Mei ;
Xiao, Jimeng .
DISCRETE APPLIED MATHEMATICS, 2021, 291 :129-142