Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is poly-time solvable for degree-3 bounded graphs and is NP-complete for degree-4 bounded graphs. But I have not been able to find any proof for this anywhere. Is it true?
What is the minimum d such that FVS in degree-d bounded graphs is NP-complete?