|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
checked on Dec 6, 2023
checked on Dec 7, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.