Thomas Kalinowski
A Recolouring Problem on Undirected Graphs
The paper is published: Rostocker Mathematisches Kolloquium, Rostock. Math. Kolloq. 58, 27-30(2004)

MSC:

05C15 Chromatic theory of graphs and maps

05C85 Graph algorithms, See also {68Q20, 68R10}

Abstract: We consider an algorithm on a graph $G=(V,E)$ with a 2-colouring
of $V$, that is motivated from the computer-aided
text-recognition. Every vertex changes simultaneously its colour
if more than a certain proportion $c$ of its neighbours have the
other colour. It is shown, that by iterating this algorithm the
colouring becomes either constant or 2-periodic.
For$c=\displaystyle\frac{1}{2}$ the presented theorem is a special case of a known
result \cite{PolSu-kal}, but here developed independently with another
motivation and a new proof.

Keywords: Chromatic theory of graphs and maps, Graph algorithms