Maximum Independent Sets in Subcubic Graphs: New Results

Ararat Harutyunyan, Michael Lampis, Vadim Lozin, Jérôme Monnot

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.

Knowledge Graph



Sign up or login to leave a comment