Covering complete graphs by monochromatically bounded sets

Abstract

Given a k-colouring of the edges of the complete graph K n , are there k - 1 monochromatic components that cover its vertices? This important special case of the well-known Lovász-Ryser conjecture is still open. In this paper we consider a strengthening of this question, where we insist that the covering sets are not merely connected but have bounded diameter. In particular, we prove that for any colouring of E(K n ) with four colours, there is a choice of sets A 1 ,A 2 ,A 3 that cover all vertices, and colours c 1 , c 2 , c 3 , such that for each i = 1, 2, 3 the monochromatic subgraph induced by the set A i and the colour c i has diameter at most 80.