Abstract

K\Honig's theorem says that the vertex cover number of every bipartite graph is at most its matching number (in fact they are equal since, trivially, the matching number is at most the vertex cover number). An equivalent formulation of K\H onig's theorem is that in every 2-coloring of the edges of a graph G, the number of monochromatic components needed to cover the vertex set of G is at most the independence number of G. We prove the following strengthening of K\Honig's theorem: In every 2-coloring of the edges of a graph G, the number of monochromatic subgraphs of bounded diameter needed to cover the vertex set of G is at most the independence number of G. © 2025 Society for Industrial and Applied Mathematics Publications. All rights reserved.