2018/03/13 by Chen Gang, Yongxin Lan, Chen, Gang +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1803.04889
openalex publication_date 2018/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a positive integer n and a planar graph H, let Tn(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 arP(n, H), is the maximum number of colors in an edge-coloring of a plane triangulation T∈ Tn(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 Mt denote a matching of size t. We prove that for all t≥6 and n≥ 3t-6, 2n+3t-15≤ ar_P(n, Mt)≤ 2n+4t-14, which significantly improves the existing lower and upper bounds for arP(n, Mt). It seems that for each t≥6, the lower bound we obtained is the exact value of ar_P(n, Mt) for sufficiently large n. This is indeed the case for M6. We prove that arP(n, M6)=2n+3 for all n≥30.