Methods of classification and algorithms of graph coloring

V.A. Perepelitsa (Zaporizhzhia National University)
I.V. Kozin (Zaporizhzhia National University)
S.V. Kurapov (Zaporizhzhia National University)


We study the connection between classifications on finite set and the problem of graph coloring. We consider the optimality criterion for classification of special type: h-classifications, which are built on the base of proximity measure. It is shown that the problem of finding the optimal h-classification can be reduced to the problem of coloring of non-adjacency graph vertices by the smallest possible number of colors. We consider algorithms of proper coloring of graph vertices.


Aivazian S.A., Bukhshtaber V.M., Eniukov I.S., Meshalkin L.D. Applied Statistics: Classification and dimensionality reduction, 1989. (in Russian)

Kozin I.V. "Fragmentary algorithms in decision making support systems", Problems of appl. math. and math. model.: Coll. sci works, Dnipropetrovsk, 2005; pp. 131-137. (in Russian)

Kozin I.V., Kurapov S.V. "Algorithms of optimal classification", Visnyk Zaporiz. nat. un-tu, 2005; 1: pp. 25-29. (in Russian)

Kim J.O., Muller Ch.U., Klekka U.R. Factor, discriminant, and cluster analysis, 1989. (in Russian)

Kristofides N. Graph Theory. Algorithmic approach, 1978. (in Russian)

Sergienko I.V. Mathematical models and methods of discrete optimization problem solving, 1988. (in Russian)




  • There are currently no refbacks.

Copyright (c) 2008 V.A. Perepelitsa, I.V. Kozin, S.V. Kurapov

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Registered in

ISSN (Online): 2664-5009
ISSN (Print): 2664-4991