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