Authors: Milićević, Luka 
Title: Covering complete graphs by monochromatically bounded sets
Journal: Applicable Analysis and Discrete Mathematics
Volume: 13
Issue: 1
First page: 85
Last page: 110
Issue Date: 1-Apr-2019
Rank: M21
ISSN: 1452-8630
DOI: 10.2298/AADM170204022M
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.
Keywords: Bounded diameter | Monochromatic component
Publisher: School of Electrical Engineering, University of Belgrade
Project: Representations of logical structures and formal languages and their application in computing 

Show full item record


checked on Jul 14, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.