Volume 17, No 6, 2010, P. 77-95

UDC 519.1
D. B. Khoroshilova
On perfect colorings of line graphs

Abstract:
The description of all feasible perfect colorings of line graphs, using two colors, is given, and all matrices of parameters of such colorings are listed. In addition, a simple construction that makes it possible to produce perfect colorings of arbitrary line graphs is proposed, and the perfect colorings which can be obtained with the use of the construction in question are characterized.
Bibl. 13.

Keywords: perfect coloring, equitable partition, line graph.

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