Premium
Rainbow Numbers for Cycles in Plane Triangulations
Author(s) -
Horňák Mirko,
Jendrol′ Stanislav,
Schiermeyer Ingo,
Soták Roman
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21803
Subject(s) - rainbow , combinatorics , mathematics , vertex (graph theory) , plane (geometry) , upper and lower bounds , colored , triangulation , enhanced data rates for gsm evolution , geometry , graph , physics , optics , mathematical analysis , computer science , telecommunications , materials science , composite material
In the article, the existence of rainbow cycles in edge colored plane triangulations is studied. It is shown that the minimum numberrb ( T n , C 3 ) of colors that force the existence of a rainbow C 3 in any n ‐vertex plane triangulation is equal to ⌊ 3 n − 4 2 ⌋ . For k ≥ 4 a lower bound and for k ∈ { 4 , 5 } an upper bound of the numberrb ( T n , C k ) is determined.