On the maximum independent set problem in subclasses of subcubic graphs

International audienceIt is known that the maximum independent set problem is NP-completefor subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, theproblem is NP-complete for 3-regular Hamiltonian graphs and forH-freesubcubic graphs wheneverHcontains a connected component which is nota tree with at most 3 leaves. We show that if every connected component ofHis a tree with at most 3 leaves and at most 7 vertices, then the problem canbe solved forH-free subcubic graphs in polynomial time. We also strengthenthe NP-completeness of the problem on 3-regular Hamiltonian graphs byshowing that the problem is APX-complete in this clas