MSC2010 05C15
Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem
D. V. Sirotkin1
| Annotation | In the paper we consider some class of replacements of subgraphs in graphs, while replacements in this class preserve $k$-colorability. One define each local transformantion from this class by a pattern – the set of partitions of a set into subsets. The paper shows that a replacing subgraph exists for any pattern, and it gives an estimation for the number of its vertices depending on size of the pattern. This is the main result of the paper, one used methods from 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. |
|---|---|
| Keywords | $k$-colourability problem, local transformation, realization problem, Shannon function |
1Dmitry V. Sirotkin, laboratory assistant, Laboratory of Theory and Practice of Decision Support Systems, National Research University Higher School of Economics (25/12 Bolshaja Pecherskaja Str., Nizhny Novgorod 603155, Russia); laboratory assistant, Department of Algebra, Geometry and Discrete Mathematics, National Research Lobachevsky University of Nizhny Novgorod (23 Gagarina avenue, Nizhny Novgorod, 603950, Russia), ORCID: http://orcid.org/ 0000-0002-2682-9867, dmitriy.v.sirotkin@gmail.com
Citation: D. V. Sirotkin, "[Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem]", Zhurnal Srednevolzhskogo matematicheskogo obshchestva,19:2 (2017) 98–104 (In Russian)
DOI 10.15507/2079-6900.19.201701.098-104
