2017/05/25 by Milićević, Luka · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1705.09370
Given a k-colouring of the edges of the complete graph Kn, 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(Kn) with 4 colours, there is a choice of sets A1, A2, A3 that cover all vertices, and colours c1, c2, c3, such that for each i = 1,2,3 the monochromatic subgraph induced by the set Ai and the colour ci has diameter at most 160.