Open AccessMethods of classification and algorithms of graph coloring
Author(s) -
V. A. Perepelitsa,
I. V. Kozin,
S.V. Kurapov
Publication year - 2021
Publication title -
researches in mathematics
Language(s) - English
Resource type - Journals
eISSN - 2664-5009
pISSN - 2664-4991
DOI - 10.15421/240816
Subject(s) - fractional coloring , greedy coloring , combinatorics , list coloring , graph coloring , complete coloring , edge coloring , mathematics , adjacency list , graph power , graph , independent set , discrete mathematics , algorithm , computer science , line graph
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.