Low Diameter Monochromatic Covers of Complete Multipartite Graphs

2021/05/14 by Sean English, English, Sean, Connor Mattes +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2105.07038

openalex publication_date 2021/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let the diameter cover number, D^t_r(G), denote the least integer d such that under any r-coloring of the edges of the graph G, there exists a collection of t monochromatic subgraphs of diameter at most d such that every vertex of G is contained in at least one of the subgraphs. We explore the diameter cover number with two colors and two subgraphs when G is a complete multipartite graph with at least three parts. We determine exactly the value of D₂²(G) for all complete tripartite graphs G, and almost all complete multipartite graphs with more than three parts.

Cited by

• Bounded diameter monochromatic component covers
• 2-reachable subsets in two-colored graphs

Related

• Covering complete graphs by monochromatically bounded sets
• Finding Large Monochromatic Diameter Two Subgraphs
• Coverings by few monochromatic pieces - a transition between two Ramsey problems
• Bounded diameter monochromatic component covers
• On Clique Coverings of Complete Multipartite Graphs