Volume 16, No 1, 2009, P. 80-92

UDC 519.87
D. B. Khoroshilova
On two-colour perfect colourings of circular graphs

Abstract:
We consider perfect colourings of a certain class of infinite graphs called circular graphs. It is shown that every such perfect colouring yields a perfect colouring of an $n$-dimensional infinite lattice which has the same parameters as the original colouring. A construction that produces two-colour perfect colourings of circular graphs is proposed and the parameters of perfect colourings given by the construction are enumerated.
Bibl. 12.

Keywords: perfect colouring, circular graph, equitable partition.

Khoroshilova Daria Borisovna ¹
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: dkhor@ngs.ru