[HTML][HTML] Planar anti-Ramsey numbers of paths and cycles

Y Lan, Y Shi, ZX Song - Discrete Mathematics, 2019 - Elsevier
Y Lan, Y Shi, ZX Song
Discrete Mathematics, 2019Elsevier
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 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∈ T n (H) such that T contains no rainbow copy of H. Analogously to anti …
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 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 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 a r P (n, H)(under the name of rainbow numbers) was initiated by Horňák 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.
Elsevier
Showing the best result for this search. See all results