An Algorithm for finding 2-colourings with Small Monochromatic Components in Graphs of Maximum Degree 4

This paper concerns improper l-colourings of graphs in which all monochromatic components (i.e., components of the subgraphs induced by the colour classes) have at most C vertices. We present and analyse an efficient algorithm which finds, for any graph G of maximum degree 4, a 2-colouring in which all monochromatic components have size at most O(2(2 log_2 n)^{1/2}) and maximum degree at most 2. The algorithm is based on simply flipping the colour of a vertex whenever there is immediate gain from doing so, and so is greedy in some sense. An algorithm that achieves a constant bound (six) on monochromatic component size is implicit in recent work of Haxell, Szab\'o and Tardos, which in turn improves a result of Alon, Ding, Oporowski and Vertigan. However the simple greedy nature of our algorithm makes it an interesting object of study in its own right, and in fact our bound on monochromatic component size applies to any 2- colouring that (roughly) cannot be improved by a single vertex colour flip. We also define the metachromatic number of a class of graphs to be the minimum l such that, for some C, every graph in the class has a colouring of the above kind. We establish a lower bound of Floor(log2(d/2 + 1)) for the metachromatic number of the class of graphs of maximum degree at most d.