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