Connected Colorings of Graphs

Abstract

Let $H=K_{k_1,k_2,\dots ,k_t}$ be a complete multipartite graph having $t\ge 3$ parts. Extending the well-known result that a simple graph $G$ or its complement, $G$, is connected, it is proved that in any coloring of the edges of $H$ with two colors, blue and red, at least one of the subgraphs induced by the blue edges or by the red edges, is connected.