Journal of Combinatorics

Volume 15 (2024)

Number 2

Low diameter monochromatic covers of complete multipartite graphs

Pages: 139 – 157

DOI: https://dx.doi.org/10.4310/JOC.2024.v15.n2.a1

Authors

Sean English (University of North Carolina, Wilmington, N.C., U.S.A.)

Grace McCourt (University of Illinois Urbana Champaign, Illinois, U.S.A.)

Connor Mattes (University of Colorado, Denver, Co., U.S.A.)

Michael Phillips (University of Colorado, Denver, Co., U.S.A.)

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 $D^2_2 (G)$ when $G$ is a complete multipartite graph. Specifically, we determine exactly the value of $D^2_2(G)$ for all complete tripartite graphs $G$, and almost all complete multipartite graphs with more than three parts.

Keywords

diameter, covers, Ryser’s conjecture

2010 Mathematics Subject Classification

Primary 05C12. Secondary 05C15.

Received 20 May 2021

Accepted 27 February 2023

Published 23 January 2024