Planar anti-Ramsey numbers of matchings

被引:13
作者
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]   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
[22]   Anti-Ramsey Numbers of Doubly Edge-Critical Graphs [J].
Jiang, Tao ;
Pikhurko, Oleg .
JOURNAL OF GRAPH THEORY, 2009, 61 (03) :210-218
[23]   Anti-Ramsey numbers for cycles in the generalized Petersen graphs [J].
Liu, Huiqing ;
Lu, Mei ;
Zhang, Shunzhe .
APPLIED MATHEMATICS AND COMPUTATION, 2022, 430
[24]   Anti-Ramsey number of matchings in r-partite r-uniform hypergraphs [J].
Xue, Yisai ;
Shan, Erfang ;
Kang, Liying .
DISCRETE MATHEMATICS, 2022, 345 (04)
[25]   Anti-Ramsey Numbers in Complete k-Partite Graphs [J].
Ding, Jili ;
Bian, Hong ;
Yu, Haizheng .
MATHEMATICAL PROBLEMS IN ENGINEERING, 2020, 2020
[26]   Anti-Ramsey Numbers of Loose Paths and Cycles in Uniform Hypergraphs [J].
Tong Li ;
Yucong Tang ;
Guanghui Wang ;
Guiying Yan .
Graphs and Combinatorics, 2025, 41 (4)
[27]   ANTI-RAMSEY NUMBER OF HANOI GRAPHS [J].
Gorgol, Izolda ;
Lechowska, Anna .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2019, 39 (01) :285-296
[28]   Anti-Ramsey numbers for trees in complete multi-partite graphs [J].
Zhang, Meiqiao ;
Dong, Fengming .
DISCRETE MATHEMATICS, 2022, 345 (12)
[29]   Anti-Ramsey problems for cycles [J].
Xu, Jiale ;
Lu, Mei ;
Liu, Ke .
APPLIED MATHEMATICS AND COMPUTATION, 2021, 408
[30]   On the anti-Ramsey number of forests [J].
Fang, Chunqiu ;
Gyori, Ervin ;
Lu, Mei ;
Xiao, Jimeng .
DISCRETE APPLIED MATHEMATICS, 2021, 291 :129-142