Monochromatic Tree Covers in Nearly Complete (Bipartite) Graphs

It is known that every 2-edge-colored complete graph K_n (respectively, complete bipartite graph K_n,m) contains two monochromatic trees whose vertices cover all the vertices of K_n (respectively, K_n,m). A natural question is that what is the largest integer t such that the following statement holds: if G is obtained from the complete graph K_n (respectively, complete bipartite graph K_n,m) by deleting t edges arbitrarily, then every 2-edge-colored G still contains two monochromatic trees whose vertices cover all the vertices of G. In this paper, we show that we can delete at most n − 1 edges in the complete graph case, and at most one edge in the complete bipartite graph case. We also construct examples showing that both results are sharp. We in fact prove these results in much stronger forms, and we also obtain some analogous results for multipartite graphs. These results generalize a result on monochromatic path covers of Gyárfás, Jagota and Schelp from 1997.