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 条
  • [1] Improved bounds for anti-Ramsey numbers of matchings in outer-planar graphs
    Pei, Yifan
    Lan, Yongxin
    He, Hua
    APPLIED MATHEMATICS AND COMPUTATION, 2022, 418
  • [2] The Outer-Planar Anti-Ramsey Number of Matchings
    Xiang, Changyuan
    Lan, Yongxin
    Yan, Qinghua
    Xu, Changqing
    SYMMETRY-BASEL, 2022, 14 (06):
  • [3] Planar anti-Ramsey numbers of paths and cycles
    Lan, Yongxin
    Shi, Yongtang
    Song, Zi-Xia
    DISCRETE MATHEMATICS, 2019, 342 (11) : 3216 - 3224
  • [4] Anti-Ramsey number of matchings in hypergraphs
    Ozkahya, Lale
    Young, Michael
    DISCRETE MATHEMATICS, 2013, 313 (20) : 2359 - 2364
  • [5] Anti-Ramsey numbers for matchings in 3-regular bipartite graphs
    Jin, Zemin
    APPLIED MATHEMATICS AND COMPUTATION, 2017, 292 : 114 - 119
  • [6] Anti-Ramsey number of matchings in a hypergraph
    Jin, Zemin
    DISCRETE MATHEMATICS, 2021, 344 (12)
  • [7] Anti-Ramsey hypergraph numbers
    Budden, Mark
    Stiles, William
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2021, 9 (02) : 397 - 407
  • [8] On degree anti-Ramsey numbers
    Gilboa, Shoni
    Hefetz, Dan
    EUROPEAN JOURNAL OF COMBINATORICS, 2017, 60 : 31 - 41
  • [9] Anti-Ramsey number of matchings in outerplanar graphs
    Jin, Zemin
    Yu, Rui
    Sun, Yuefang
    DISCRETE APPLIED MATHEMATICS, 2024, 345 : 125 - 135
  • [10] Anti-Ramsey numbers of small graphs
    Bialostocki, Arie
    Gilboa, Shoni
    Roditty, Yehuda
    ARS COMBINATORIA, 2015, 123 : 41 - 53