Geodesic
A constructive existence theorem related to local transformations of graphs for the independent set problem
Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 21 (2019) no. 2, pp. 215-221.

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

For a given graph, the independent set problem is to find the size of a maximum set of pairwise non-adjacent its vertices. There are numerous cases of NP-hardness and polynomial-time solvability of this problem. To determine a computational status of the independent set problem, local transformations of graphs are often used. The paper considers some class of replacements of subgraphs in graphs that change the independence number in a controllable way. Every such local transform of a graph is determined by some pattern which is a subset of the power set. It is obvious that this pattern must be gradable. The paper shows that replacing subgraph exists for any gradable pattern.
Keywords: independent set problem, graph with given properties.
Mots-clés : local transformation 
@article{SVMO_2019_21_2_a4,
     author = {D. V. Sirotkin and D. S. Malyshev},
     title = {A constructive existence theorem related to local transformations of graphs for the independent set problem},
     journal = {\v{Z}urnal Srednevol\v{z}skogo matemati\v{c}eskogo ob\^{s}estva},
     pages = {215--221},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/}
}
TY  - JOUR
AU  - D. V. Sirotkin
AU  - D. S. Malyshev
TI  - A constructive existence theorem related to local transformations of graphs for the independent set problem
JO  - Žurnal Srednevolžskogo matematičeskogo obŝestva
PY  - 2019
SP  - 215
EP  - 221
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/
LA  - ru
ID  - SVMO_2019_21_2_a4
ER  - 
%0 Journal Article
%A D. V. Sirotkin
%A D. S. Malyshev
%T A constructive existence theorem related to local transformations of graphs for the independent set problem
%J Žurnal Srednevolžskogo matematičeskogo obŝestva
%D 2019
%P 215-221
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/
%G ru
%F SVMO_2019_21_2_a4
D. V. Sirotkin; D. S. Malyshev. A constructive existence theorem related to local transformations of graphs for the independent set problem. Žurnal Srednevolžskogo matematičeskogo obŝestva, Tome 21 (2019) no. 2, pp. 215-221. http://geodesic.mathdoc.fr/item/SVMO_2019_21_2_a4/

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

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

[3] 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 Russ) | Zbl

[4] D. V. Sirotkin, “On the complexity for constructing a 3-colouring for planar graphs with short facets”, Zhurnal Srednevolzhskogo matematicheskogo obshchestva, 20:2 (2018), 199–205 (in Russ)

[5] D. V. Sirotkin, D. S. Malyshev, “A method of graph reduction and its applications”, Discrete Mathematics and Applications, 28:4 (2018), 249–258 | DOI | MR | Zbl

[6] D. S. Malyshev, D. V. Sirotkin, “Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs”, Journal of Applied and Industrial Mathematics, 11:3 (2017), 400–414 | DOI | MR | Zbl

[7] D. V. Sirotkin, D. S. Malyshev, “On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size”, Journal of Applied and Industrial Mathematics, 25:4 (2018), 759–769 | DOI | MR

[8] 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

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

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

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