Lozin, Vadim Monnot, Jérôme Ries, Bernard 2014 It is known that the maximum independent set problem is NP-complete for subcubic graphs, i.e. graphs of vertex degree at most 3. Moreover, the problem is NP-complete for 3-regular Hamiltonian graphs and for H-free subcubic graphs whenever H contains a connected component which is not a tree with at most 3 leaves. We show that if every connected component of His a tree with at most 3 leaves and at most 7 vertices, then the problem can be solved for H-free subcubic graphs in polynomial time. We also strengthen the NP-completeness of the problem on 3-regular Hamiltonian graphs by showing that the problem is APX-complete in this class. application/pdf https://folia.unifr.ch/global/documents/322639 https://folia.unifr.ch/documents/322639/files/independentset.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jda.2014.08.005 info:eu-repo/semantics/altIdentifier/issn/1570-8667 info:eu-repo/semantics/openAccess Rights reserved Journal of Discrete Algorithms. - Elsevier BV. - 2014, vol. 31, p. 104-112 Computational Theory and Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Independent set Polynomial-time algorithm Subcubic graph APX-completeness info:eu-repo/classification/udc/004 On the maximum independent set problem in subclasses of subcubic graphs http://purl.org/coar/resource_type/c_6501