Kalinowski, Thomas

2004

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.

Rostocker Mathematisches Kolloquium, v.58, p. 27-30

2363-6106

0138-3248

https://hdl.handle.net/1959.11/26787

Universitaet Rostock, Fachbereich Mathematik

A Recolouring Problem on Undirected Graphs

Journal Article

Publication