Covering complete graphs by monochromatically bounded sets

DOI10.2298/AADM170204022MMaRDI QIDQ5028797zbMATH OpenOpenAlexWikidataFDO

Authors Luka Milićević

Publication date 10 February 2022

Published in Applicable Analysis and Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09370

zbMATH Keywords

bounded diametermonochromatic component

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

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'asz-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 4 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 160.

Recommendations

• Monochromatic diameter-2 components in edge colorings of the complete graph
• Vertex coverings by monochromatic cycles and trees
• Large monochromatic components of small diameter
• One-sided coverings of colored complete bipartite graphs
• scientific article; zbMATH DE number 4154488

Cites work

• Commuting contractive families
• scientific article; zbMATH DE number 3616474 (Why is no real title available?)
• Large components in r-edge-colorings of K_n have diameter at most five
• Large monochromatic components in edge colorings of graphs: A survey
• Large monochromatic triple stars in edge colourings
• Ryser's conjecture for tripartite 3-graphs
• Vertex covers by monochromatic pieces -- a survey of results and problems

Cited in

(12)

• Generalizations and strengthenings of Ryser's conjecture
• Monochromatic diameter-2 components in edge colorings of the complete graph
• Cover \(k\)-uniform hypergraphs by monochromatic loose paths
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• Large components in r-edge-colorings of K_n have diameter at most five
• scientific article; zbMATH DE number 15152 (Why is no real title available?)
• Large monochromatic components of small diameter
• Low diameter monochromatic covers of complete multipartite graphs
• A bounded diameter strengthening of Kőnig's theorem
• 2-reachable subsets in two-colored graphs
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• Bounded diameter monochromatic component covers

This page was built for publication: Covering complete graphs by monochromatically bounded sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028797)