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 | 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. |
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
SCOPUSTM
Citations
1
checked on Sep 15, 2024
Page view(s)
9
checked on Sep 16, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.