Premium
Edge‐colorings avoiding rainbow stars
Author(s) -
Hoppen Carlos,
Lefmann Hanno,
Odermann Knut,
Sanches Juliana
Publication year - 2018
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.22165
Subject(s) - combinatorics , rainbow , mathematics , vertex (graph theory) , edge coloring , greedy coloring , graph , complete coloring , discrete mathematics , line graph , graph power , physics , quantum mechanics
We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given r ≥ t ≥ 2 , we look for n ‐vertex graphs that admit the maximum number of r ‐edge‐colorings such that at most t − 1 colors appear in edges incident with each vertex, that is, r ‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n , we show that, with the exception of the case t = 2 , the complete graph K n is always the unique extremal graph. We also consider generalizations of this problem.