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/

[1] M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Mir Publ., Moscow, 1982, 416 pp. (In Russ.) | MR

[2] V. E. Alekseev, V. V. Lozin, “On local transformations of graphs that preserve the independence number”, Diskretnyi Analiz i Issledovanie Operatsii, 5:1 (1998), 3–19 (In Russ.) | MR | Zbl

[3] V. E. Alekseev, V. V. Lozin, “Local transformations of graphs preserving independence number”, Discrete Applied Mathematics, 135 (2004), 16–29 | MR

[4] V. E. Alekseev, D. S. Malyshev, “Planar graph classes with the independent set problem solvable in polynomial time”, Journal of Applied and Industrial Mathematics, 3:1 (2008), 1–5 | DOI | MR

[5] B. Lévêque, D. de Werra, “Graph transformations preserving the stability number”, Discrete Applied Mathematics, 160:18 (2012), 2752–2759 | DOI | MR | Zbl

[6] V. V. Lozin, “Conic reduction of graphs for the stable set problem”, Discrete Mathematics, 222:1–3 (2000), 199–211 | DOI | MR | Zbl

[7] V. V. Lozin, “Stability preserving transformations of graphs”, Annals of Operations Research, 188 (2011), 331–341 | DOI | MR | Zbl

[8] D. S. Malyshev, “Classes of subcubic planar graphs for which the independent set problem is polynomially solvable”, Journal of Applied and Industrial Mathematics, 7:2 (2013), 221–228 | DOI | MR