×

The existence and uniqueness theorems associated with local transformations of graphs for the \(k\)-colorability problem. (Russian. English summary) Zbl 1399.05088

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.

MSC:

05C15 Coloring of graphs and hypergraphs
05A18 Partitions of sets
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite