Sirotkin, D. V. The existence and uniqueness theorems associated with local transformations of graphs for the \(k\)-colorability problem. (Russian. English summary) Zbl 1399.05088 Zh. Sredn. Mat. Obshch. 19, No. 2, 98-104 (2017). Using the methods of graph theory and combinatorial analysis, the author solves the realization problem for the \(k\)-colorability problem. It is shown that for every \(n\), \(k\geq 3\) and an arbitrary family \(\rho\) of pairwise distinct partitions of a set \(A\) of \(n\) elements into not more than 5 non-empty parts there exists a graph \(G\) and a subset \(A\subseteq V(G)\) such that \(\mathfrak M_{\chi,k}(G,A)=\rho\). Here, \(\mathfrak M_{\xi,k}(H,A)\) is a family of all such sets \(X\subseteq A\) that for any \(Y\subset X\) the inequality \(\alpha(H\setminus X)<\alpha(H\setminus Y)\) is true. \(\alpha(G)\) denotes the independence number of graph \(G\). An estimation of the number of vertices in the graph \(G(\rho)\) is given. Reviewer: Boris V. Loginov (Ul’yanovsk) MSC: 05C15 Coloring of graphs and hypergraphs 05A18 Partitions of sets 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:\(k\)-colorability problem; local transformation; realization problem; Shannon function PDFBibTeX XMLCite \textit{D. V. Sirotkin}, Zh. Sredn. Mat. Obshch. 19, No. 2, 98--104 (2017; Zbl 1399.05088)