2017/09/04 by Yongxin Lan, Yongtang Shi, Lan, Yongxin +3 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1709.00970
openalex publication_date 2017/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by anti-Ramsey numbers introduced by Erdős, Simonovits and Sós in 1975, we study the anti-Ramsey problem when host graphs are plane triangulations. 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. Analogous to anti-Ramsey numbers and Turán numbers, planar anti-Ramsey numbers are closely related to planar Turán numbers, where the planar Turán number of H is the maximum number of edges of a planar graph on n vertices without containing H as a subgraph. The study of arP(n, H) (under the name of rainbow numbers) was initiated by Horňák, Jendrol', Schiermeyer and Soták [J Graph Theory 78 (2015) 248--257]. In this paper we study planar anti-Ramsey numbers for paths and cycles. We first establish lower bounds for arP(n, Pk) when n≥ k≥8. We then improve the existing lower bound for arP(n, Ck) when k≥ 5 and n≥ k2-k. Finally, using the main ideas in the above-mentioned paper, we obtain upper bounds for arP(n, C6) when n≥8 and arP(n, C7) when n≥ 13, respectively.