Vol. 14, No. 3, 2021

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Monochromatic diameter-2 components in edge colorings of the complete graph

Miklós Ruszinkó, Lang Song and Daniel P. Szabo

Vol. 14 (2021), No. 3, 377–386
Abstract

Gyárfás conjectured that in every $r$-edge-coloring of the complete graph ${K}_{n}$ there is a monochromatic component on at least $n∕\left(r-1\right)$ vertices which has diameter at most 3. We show that for $r=3,4,5$ and $6$ a diameter of 3 is best possible in this conjecture, constructing colorings where every monochromatic diameter-2 subgraph has strictly less than $n∕\left(r-1\right)$ vertices.

Keywords
Ramsey theory, edge colorings, graph theory, combinatorics, monochromatic components, graph factorization
Mathematical Subject Classification 2010
Primary: 05C15, 05C51, 05C55, 05D10