Monochromatic diameter-2 components in edge colorings of the complete graph

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

doi:10.2140/involve.2021.14.377

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

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

DOI: 10.2140/involve.2021.14.377

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 ∕ (r - 1)$ 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 ∕ (r - 1)$ vertices.

Keywords

Ramsey theory, edge colorings, graph theory, combinatorics, monochromatic components, graph factorization

Mathematical Subject Classification 2010

Primary: 05C15, 05C51, 05C55, 05D10

Milestones

Received: 14 November 2019

Revised: 26 September 2020

Accepted: 17 January 2021

Published: 17 July 2021

Communicated by Ann N. Trenk

Authors

Miklós Ruszinkó
Alfréd Rényi Institute of Mathematics Budapest Hungary	Faculty of Information Technology and Bionics Pázmány Péter Catholic University Budapest Hungary

Lang Song
Department of Mathematics Grinnell College Grinnell, IA United States

Daniel P. Szabo
Department of Computer Science University of Wisconsin Madison, WI United States

Vol. 14, No. 3, 2021