Covering Complete Graphs by Monochromatically Bounded Sets

Applicable Analysis and Discrete Mathematics

article

Luka Milicevic¹ 

[1] Mathematical Institute of the Serbian Academy of Sciences and Arts

关键词: monochromatic component;    bounded diameter;   

DOI  :  10.2298/AADM170204022M

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

Given a k-colouring of the edges of the complete graph Kn, are there k − 1monochromatic components that cover its vertices? This important specialcase of the well-known Lov´asz-Ryser conjecture is still open. In this paper weconsider a strengthening of this question, where we insist that the coveringsets are not merely connected but have bounded diameter. In particular, weprove that for any colouring of E(Kn) with four colours, there is a choiceof sets A1, A2, A3 that cover all vertices, and colours c1, c2, c3, such that foreach i = 1, 2, 3 the monochromatic subgraph induced by the set Ai and thecolour ci has diameter at most 80.

【 授权许可】

Unknown