However, Brandstädt et al. [@BBKNP13] proved that [Near-Bipartiteness]{} remains [[NP]{}]{}-complete for perfect graphs. The same authors also showed that [Near-Bipartiteness]{} is polynomial-time solvable for $P_4$-free graphs.

Yang and Yuan [@YY06] proved that [Near-Bipartiteness]{} also remains [[NP]{}]{}-complete for graphs of maximum degree $4$. To complement their hardness result, Yang and Yuan [@YY06] showed that every connected graph of maximum degree at most $3$ is near-bipartite except the complete graph $K_4$ on four vertices. This also follows from a more general result of Catlin and Lai [@CL95]. Recently we gave a linear-time algorithm for finding an independent feedback vertex set in a graph of maximum degree at most $3$ [@BDFJP17], and also proved that [Near-Bipartiteness]{} is [[NP]{}]{}-complete even for line graphs of maximum degree $4$ [@BDFJP17b]. It is also known that [Near-Bipartiteness]{} is [[NP]{}]{}-complete for planar graphs; this follows from a result of Dross, Montassier and Pinlou [@DMP16]; see the arXiv version of [@BDFJP17] for details.

Tamura, Ito and Zhou [@TIZ15] proved that [Independent Feedback Vertex Set]{} is [[NP]{}]{}-complete for planar bipartite graphs of maximum degree $4$ (note that [Near-Bipartiteness]{} is trivial for bipartite graphs). They also proved that [Independent Feedback Vertex Set]{} is linear-time solvable for graphs of bounded treewidth, chordal 