DC Field | Value | Language |
---|---|---|
dc.contributor.author | Milićević, Luka | en |
dc.date.accessioned | 2020-05-01T20:12:38Z | - |
dc.date.available | 2020-05-01T20:12:38Z | - |
dc.date.issued | 2019-04-01 | en |
dc.identifier.issn | 1452-8630 | en |
dc.identifier.uri | http://researchrepository.mi.sanu.ac.rs/handle/123456789/1042 | - |
dc.description.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. | en |
dc.publisher | School of Electrical Engineering, University of Belgrade | - |
dc.relation | Representations of logical structures and formal languages and their application in computing | - |
dc.relation.ispartof | Applicable Analysis and Discrete Mathematics | en |
dc.subject | Bounded diameter | Monochromatic component | en |
dc.title | Covering complete graphs by monochromatically bounded sets | en |
dc.type | Article | en |
dc.identifier.doi | 10.2298/AADM170204022M | en |
dc.identifier.scopus | 2-s2.0-85065543292 | en |
dc.relation.firstpage | 85 | en |
dc.relation.lastpage | 110 | en |
dc.relation.issue | 1 | en |
dc.relation.volume | 13 | en |
dc.description.rank | M21 | - |
item.grantfulltext | none | - |
item.cerifentitytype | Publications | - |
item.fulltext | No Fulltext | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
item.openairetype | Article | - |
crisitem.project.projectURL | http://www.mi.sanu.ac.rs/novi_sajt/research/projects/174026e.php | - |
crisitem.project.fundingProgram | Directorate for Social, Behavioral & Economic Sciences | - |
crisitem.project.openAire | info:eu-repo/grantAgreement/NSF/Directorate for Social, Behavioral & Economic Sciences/1740267 | - |
crisitem.author.orcid | 0000-0002-1427-7241 | - |
SCOPUSTM
Citations
1
checked on Sep 7, 2024
Page view(s)
1
checked on Sep 7, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.