Monochromatic Path Covers in Nearly Complete Graphs

Abstract

It is known that in every 2-coloring of the edges of the complete graph there exist two vertex disjoint paths—one red, one blue—that collectively cover all the vertices. In this paper, analogous existence and efficiency questions are examined when edges are missing from the complete graph. The main result shows the existence of a path cover when at most $\lfloor n/2\rfloor$ edges are missing. An example shows this result is sharp. A second result shows that a path cover can be found efficiently if a matching is missing.