Maximum independent sets in graphs of low degree
Vadim Lozin, Martin Milanič · PUB – Publications at Bielefeld University (Bielefeld University) · 2007
We study computational complexity of the maximum independent set problem on graphs of bounded vertex degree. In general, this problem is NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify three graph properties to which the complexity of the problem is sensible.