Planar anti-Ramsey numbers of paths and cycles

Motivated by anti-Ramsey numbers introduced by Erdős, Simonovits and Sos 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 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 a r P ( n , H ) , is the maximum number of colors in an edge-coloring of a plane triangulation T ∈ T n ( H ) such that T contains no rainbow copy of H . Analogously to anti-Ramsey numbers and Turan numbers, planar anti-Ramsey numbers are closely related to planar Turan numbers, where the planar Turan 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 a r P ( n , H ) (under the name of rainbow numbers) was initiated by Horňak et al. (2015). In this paper we study planar anti-Ramsey numbers for paths and cycles. We first improve existing lower bound for a r P ( n , C k ) when k ≥ 5 and n ≥ k 2 − k . Then, using the main ideas in the above-mentioned paper, we obtain upper bounds for a r P ( n , C 6 ) when n ≥ 8 and a r P ( n , C 7 ) when n ≥ 13 , respectively. Finally, we establish lower bounds for a r P ( n , P k ) when n ≥ k ≥ 8 .