Geodesic
Independent sets in graphs without subtrees with many leaves
Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 1, pp. 5-16.

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

A subtree of a graph is called inscribed if there is no three vertices in the subtree inducing a triangle in the graph. We prove that for any fixed k the independent set problem is solvable in polynomial time for each of the following classes of graphs: 1) the graphs without subtrees with $k$ leaves, 2) the subcubic graphs without inscribed subtrees with $k$ leaves, 3) the graphs with degrees not exceeding $k$ without induced subtrees with 4 leaves. Ill. 1, bibliogr. 12.
Keywords: graph, independent set, forbidden subtree
Mots-clés : polynomial algorithm. 
@article{DA_2016_23_1_a0,
     author = {V. E. Alekseev and D. V. Zakharova},
     title = {Independent sets in graphs without subtrees with many leaves},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--16},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2016_23_1_a0/}
}
TY  - JOUR
AU  - V. E. Alekseev
AU  - D. V. Zakharova
TI  - Independent sets in graphs without subtrees with many leaves
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2016
SP  - 5
EP  - 16
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2016_23_1_a0/
LA  - ru
ID  - DA_2016_23_1_a0
ER  - 
%0 Journal Article
%A V. E. Alekseev
%A D. V. Zakharova
%T Independent sets in graphs without subtrees with many leaves
%J Diskretnyj analiz i issledovanie operacij
%D 2016
%P 5-16
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2016_23_1_a0/
%G ru
%F DA_2016_23_1_a0
V. E. Alekseev; D. V. Zakharova. Independent sets in graphs without subtrees with many leaves. Diskretnyj analiz i issledovanie operacij, Tome 23 (2016) no. 1, pp. 5-16. http://geodesic.mathdoc.fr/item/DA_2016_23_1_a0/

[1] V. E. Alekseev, “A polynomial algorithm for finding the largest independent sets in claw-free graphs”, Diskretn. Anal. Issled. Oper., Ser. 1, 6:4 (1999), 3–19 | MR | Zbl

[2] V. E. Alekseev, D. V. Zakharova, “Independent sets in the graphs with bounded minors of the extended incidence matrix”, J. Appl. Ind. Math., 5:1 (2011), 14–18 | DOI | MR | Zbl

[3] V. E. Alekseev, D. V. Korobitsyn, “Complexity of some problems on hereditary classes of graphs”, Diskretn. Mat., 4:4 (1992), 34–40 | MR | Zbl

[4] V. E. Alekseev, D. S. Malyshev, “Planar graph classes with the independent set problem solvable in polynomial time”, J. Appl. Ind. Math., 3:1 (2009), 1–4 | DOI | MR | Zbl

[5] V. E. Alekseev, V. A. Talanov, Graphs and Algorithms. Data Structures. Computation Models, Internet-Univ. Inform. Tekhnol., BINOM. Lab. Znanii, Moscow, 2006

[6] A. V. Bankevich, D. V. Karpov, “Bounds of the number of leaves of spanning trees”, J. Math. Sci. (New York), 184:5 (2012), 564–572 | DOI | MR | Zbl

[7] D. V. Zakharova, “Weighted independent sets in graphs with bounded minors of the extended incidence matrix”, Proc. X Int. Seminar “Discrete Math. and Its Applications” (Moscow, Russia, Jan. 1–6, 2010), Izd. Mekh.-Mat. Fak. MGU, Moscow, 2010, 303–305

[8] D. S. Malyshev, “Classes of subcubic planar graphs for which the independent set problem is polynomially solvable”, J. Appl. Ind. Math., 7:4 (2013), 537–548 | DOI | MR | Zbl

[9] V. N. Shevchenko, Qualitative Problems in Integer Programming, Nauka, Moscow, 1995 | MR

[10] Erdös P., Szekeres G., “A combinatorial problem in geometry”, Compos. Math., 2 (1935), 463–470 | MR

[11] Minty G. J., “On maximal independent sets of vertices in claw-free graphs”, J. Comb. Theory, Ser. B, 28 (1980), 284–304 | DOI | MR | Zbl

[12] Sbihi N., “Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile”, Discrete Math., 29:1 (1980), 53–76 | DOI | MR | Zbl