Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem

In the paper we consider some class of subgraphs’ replacements in graphs. These while replacements in this class preserve $k$-colorability. Every local transformantion from this class is defined by a pattern that is a collection of partitions of a set into subsets. The paper shows that a replacing subgraph exists for every pattern. An estimation is given for the number of its vertices depending on size of the pattern. This is the main result of the paper, to obtain it we used methods of graph theory and combinatorial analysis. Said class of replacements might be useful for creating polynomial reductions for the $k$-colorability problem. In particular, together with main result of the paper one can use it for input reduction for solving the $k$-colorability problem.