a [*near-bipartite decomposition*]{}. This leads to the following two related decision problems.

[.99]{} <span style="font-variant:small-caps;">[Near-Bipartiteness]{}</span>\

  ----------------- ----------------------------------------------------------------------------------------
    *    Instance:* [a graph $G$.]{}
        *Question:* [is $G$ near-bipartite (that is, does $G$ have an independent feedback vertex set)?]{}
  ----------------- ----------------------------------------------------------------------------------------

[.99]{} <span style="font-variant:small-caps;">[Independent Feedback Vertex Set]{}</span>\

  ----------------- ---------------------------------------------------------------------------
    *    Instance:* [a graph $G$ and an integer $k\geq 0$.]{}
        *Question:* [does $G$ have an independent feedback vertex set of size at most $k$?]{}
  ----------------- ---------------------------------------------------------------------------

Setting $k=n$ shows that the latter problem is more general than the first problem. Thus, if [Near-Bipartiteness]{} is [[NP]{}]{}-complete for some graph class, then so is [Independent Feedback Vertex Set]{}, and if [Independent Feedback Vertex Set]{} is polynomial-time solvable for some graph class, then so is [Near-Bipartiteness]{}.

Note that every near-bipartite graph is $3$-colourable, that is, its vertices can be coloured with at most three colours such that no two adjacent vertices are coloured alike. The problems [$3$-Colouring]{} [@Lo73] and [Near-Bipartiteness]{} [@BLS98] (and thus [Independent Feedback Vertex Set]{}) are [[NP]{}]{}-complete. However, their complexities do not necessarily coincide on special graph classes. Grötschel, Lovász and Schrijver [@GLS84] proved that [Colouring]{} is polynomial-time solvable for perfect graphs even if the permitted number of colours $k$ is part of the input. 