Edge‐colorings avoiding rainbow stars. Issue 4 (30th May 2017)

• Record Type: Journal Article
• Authors: Hoppen, Carlos; Lefmann, Hanno; Odermann, Knut; Sanches, Juliana
• Is Part Of: Journal of graph theory. Volume 87:Issue 4(2018)
• Page Start: 399
• Page End: 429
• Publication Date: 2017-05-30
• Subjects: extremal graph theory -- edge‐colorings; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22165
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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.