共 50 条
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
相关论文