On graphs with a large number of edge-colorings avoiding a rainbow triangle. (December 2017)

• Record Type: Journal Article
• Authors: Hoppen, Carlos; Lefmann, Hanno; Odermann, Knut
• Is Part Of: European journal of combinatorics. Volume 66(2017)
• Page Start: 168
• Page End: 190
• Publication Date: 2017-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.06.022
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: Inspired by previous work of Balogh (2006), we show that, given r ≥ 5 and n large, the balanced complete bipartite graph K n ∕ 2, n ∕ 2 is the n -vertex graph that admits the largest number of r -edge-colorings for which there is no triangle whose edges are assigned three distinct colors. Moreover, we extend this result to lower values of n when r ≥ 10, and we provide approximate results for r ∈ { 3, 4 } .