Geodesic
Complexity of some problems on hereditary classes of graphs
Diskretnaya Matematika, Tome 2 (1990) no. 3, pp. 90-96.

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

The independent set problem, the dominating set problem and the problem of the longest path are investigated for classes of graphs determined by finite sets of forbidden subgraphs. It is proved that if among the forbidden subgraphs there is a graph in which each connected component is homeomorphic to $K_2$ or to $K_{1,3}$, then each of these three problems is solved for graphs from such a class in polynomial time. If there are no such forbidden graphs, then all three problems remain NP-hard. 
@article{DM_1990_2_3_a9,
     author = {D. V. Korobitsyn},
     title = {Complexity of some problems on hereditary classes of graphs},
     journal = {Diskretnaya Matematika},
     pages = {90--96},
     publisher = {mathdoc},
     volume = {2},
     number = {3},
     year = {1990},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1990_2_3_a9/}
}
TY  - JOUR
AU  - D. V. Korobitsyn
TI  - Complexity of some problems on hereditary classes of graphs
JO  - Diskretnaya Matematika
PY  - 1990
SP  - 90
EP  - 96
VL  - 2
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1990_2_3_a9/
LA  - ru
ID  - DM_1990_2_3_a9
ER  - 
%0 Journal Article
%A D. V. Korobitsyn
%T Complexity of some problems on hereditary classes of graphs
%J Diskretnaya Matematika
%D 1990
%P 90-96
%V 2
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1990_2_3_a9/
%G ru
%F DM_1990_2_3_a9
D. V. Korobitsyn. Complexity of some problems on hereditary classes of graphs. Diskretnaya Matematika, Tome 2 (1990) no. 3, pp. 90-96. http://geodesic.mathdoc.fr/item/DM_1990_2_3_a9/