Independent sets in graphs without subtrees with many leaves |
| |
Authors: | V E Alekseev D V Zakharova |
| |
Institution: | 1.Lobachevsky State University of Nizhny Novgorod,Nizhny Novgorod,Russia |
| |
Abstract: | A subtree of a graph is called inscribed if no three vertices of the subtree generate a triangle in the graph. We prove that, for fixed k, the independent set problem is solvable in polynomial time for each of the following classes of graphs: (1) graphs without subtrees with k leaves, (2) subcubic graphs without inscribed subtrees with k leaves, and (3) graphs with degree not exceeding k and lacking induced subtrees with four leaves. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|