Connected Colorings of Graphs

Abstract

Let \(H = K_{k_1,k_2,\ldots,k_t}\) be a complete multipartite graph having \(t \geq 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.