Complexity of some problems on hereditary classes of graphs

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 $\rm{NP}$-hard.