A mathematical preprint establishes the exact limit for a covering problem in graph theory: every 2-colored complete bipartite graph can be covered by two monochromatic subgraphs, each with diameter at most three. In plain language, the two single-color pieces together contain all the graph's vertices, and within either piece no two vertices are more than three links apart. The result is expressed as f(2) = 3, meaning that three is the optimal universal bound in the two-color case.
The question is universal and ranges over the whole class of 2-colored complete bipartite graphs. In ordinary terms, the vertices are divided into two parts with all cross-part links present, and the links receive one of two colors. The paper targets three as the best possible covering-diameter value.
How the proof narrows the field
To establish the result, the proof looks for a minimal counterexample. It assumes a graph fails to meet the desired cover and chooses a counterexample as small as possible. The structural analysis then rules out special or equivalent vertices and neighborhood inclusion between distinct vertices. Any minimal counterexample left by that process must have either Type I or Type II structure.
For a reduced Type I coloring that is not strong, the paper gives a cover with a double star in one color and a subgraph in the other color whose diameter is at most three. A double star is a subgraph built around two joined centers.
The strong Type I case also has a good cover. For Type II colorings, the proof guarantees a cover by a double star and another monochromatic subgraph of diameter at most three.
Under the stated neighborhood conditions, a base-edge construction gives a red double star and a specified blue subgraph that together form a good cover.
Where stronger versions stop
The number three is not only an upper limit. An explicit construction shows that any cover of its vertices by two monochromatic subgraphs must include one subgraph of diameter at least three. In the notation used for the problem, this gives f(2) >= 3, matching the theorem's f(2) = 3.
The examples also mark the boundary of stronger demands. In one construction, no good cover by two double stars is possible, and every good cover uses two subgraphs of the same color. A star and a six-cycle form a cover in that construction.
A different limitation appears after deleting vertex 4 from the preceding construction: every good cover in the resulting graph uses subgraphs of different colors.
The question left on the table
The authors also state that every graph in this class has a good cover with at least one subgraph of radius at most two. In ordinary language, one piece has a center from which all its vertices are within two links. Outside the specified strong Type I case, one covering subgraph can be a double star.
An open question in the preprint asks whether every 2-colored complete bipartite graph can be covered by one double star and a second monochromatic subgraph of diameter at most three.
A corollary extends the diameter-three statement to every 2-colored complete multipartite graph with at least two parts: two monochromatic subgraphs suffice, each with diameter at most three.
The document is an arXiv preprint, version 1. Its front matter shows dates of Aug. 25 and Aug. 27, 2026.
Paper data and sources
Original title: Bounded diameter covering of 2-colored complete bipartite graphs
Authors: Louis DeBiasio, András Gyárfás, Gábor N. Sárközy
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text