2022/04/24 by David Conlon, Conlon, David, Sammy Luo +3 · 1 citation
Computer Science · Mathematics · #05C15 #05C35 #05C40 #05C55 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2204.11360
openalex publication_date 2022/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an r-edge-coloring of the complete graph Kn, what is the largest number of edges in a monochromatic connected component? This natural question has only recently received the attention it deserves, with work by two disjoint subsets of the authors resolving it for the first two special cases, when r = 2 or 3. Here we introduce a general framework for studying this problem and apply it to fully resolve the r = 4 case, showing that any 4-edge-coloring of Kn contains a monochromatic component with at least (1)/(12)\binomn2 edges, where the constant (1)/(12) is optimal only when the coloring matches a certain construction of Gyárfás.