Geodesic
Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 19 (2017) no. 2, pp. 98-104

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: $k$-colourability problem, realization problem, Shannon function.
Mots-clés : local transformation 
@article{SVMO_2017_19_2_a8,
     author = {D. V. sirotkin},
     title = {Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {98--104},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a8/}
}
TY  - JOUR
AU  - D. V. sirotkin
TI  - Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2017
SP  - 98
EP  - 104
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a8/
LA  - ru
ID  - SVMO_2017_19_2_a8
ER  - 
%0 Journal Article
%A D. V. sirotkin
%T Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2017
%P 98-104
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a8/
%G ru
%F SVMO_2017_19_2_a8
D. V. sirotkin. Theorems of existence and sufficiency connected with local transformations of graphs for the $k$-colourability problem. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 19 (2017) no. 2, pp. 98-104. http://geodesic.mathdoc.fr/item/SVMO_2017_19_2_a8/