Maximum Independent Sets in Subcubic Graphs: New Results

10/25/2018

∙

by   Ararat Harutyunyan, et al.

∙

0

∙

share

The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subclass of subcubic graphs generalizing several previously known results.