MIS complexity in cubic triangle-free graphs The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the question Independent set on cubic triangle-free graphs, it is claimed that a more general problem - maximum independent set in triangle-free cubic graphs (not necessarily planar) - is NP-complete. Could you please provide a reference to the paper for that result?
(Note that the answer to the first of the mentioned questions provides a paper where MIS is shown to be NP-hard in triangle-free planar graphs with vertices of degree &lt;= 3, and I am asking for 3-regular graphs.)
Update: There has appeared a new answer in there since, and it addresses this question as well. The note &quot;NP-complete problems on a 3-connected cubic planar graph and their applications&quot; by Ryuhei Uehara contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.
The paper &quot;The Vertex-Disjoint Triangles Problem&quot; (http://link.springer.com/chapter/10.1007/10692760_3) by Guruswami et al. has the proof of its NP-completeness as Theorem 3.
Update: As stated in a more recent answer to Complexity of Independent Set on Triangle-Free Planar Cubic Graphs, there is a note &quot;NP-complete problems on a 3-connected cubic planar graph and their applications&quot; by Ryuhei Uehara that contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.