A Recolouring Problem on Undirected Graphs

Abstract

We consider an algorithm on a graph 𝐺 = (𝑉, 𝐸) with a 2-colouring of 𝑉, that is motivated from the computer-aided text-recognition. Every vertex changes simultaneously its colour if more than a certain proportion 𝑐 of its neighbours have the other colour. It is shown, that by iterating this algorithm the colouring becomes either constant or 2-periodic. For 𝑐 = ½ the presented theorem is a special case of a known result [1], but here developed independently with another motivation and a new proof.