logo_acta

Acta Mathematica Vietnamica

On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree

icon-email Ngoc C. Lê , Trung Tran

Abstract

We consider the maximum independent set (MIS) problem, i.e., the problem asking for a vertex subset of maximum cardinality of a graph such that no two vertices in this set are adjacent. The problem is known to be NP-hard in general, even if restricted on graphs of maximum degree at most Δ for a given integer Δ3, i.e., every vertex is of degree at most Δ. We try to figure out some bounded maximum degree graph classes, under which the problem can be solved in polynomial time.