Volume 16, No 5, 2009, P. 19-25

UDC 519.17
V. E. Alekseev, S. V. Sorochan
On the entropy minimal hereditary classes of coloured graphs

Abstract:
We consider hereditary classes of graphs with coloured edges. The class is called entropy minimal if it does not contain proper hereditary subclasses having the same entropy value (logarithmic density). It is known for simple graphs that, for arbitrary fixed $a$ and $b$, the class consisting of all graphs admitting a partition by $a$ cliques and $b$ independent sets is entropy minimal. We prove a generalization of this statement for coloured graphs.
Bibl. 5.

Keywords: hereditary class, entropy, entropy minimal class.

Alekseev Vladimir Evgenyevich ¹
Sorochan Sergey Vladimirovich ¹
1. Nizhny Novgorod State University,
23 Gagarin ave., 603950 Nizhny Novgorod, Russia
e-mail: ave@uic.nnov.ru, svs-05@mail.ru