The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2.

The Colouring problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is ( H 1 , H 2 ) -free if it has no induced subgraph isomorphic to H 1 or H 2 . A connected graph H 1 is almost classified if Colouring on ( H 1 , H 2 ) -free graphs is known to be polynomial-time solvable or NP -complete for all but finitely many connected graphs H 2 . We show that every connected graph H 1 apart from the claw K 1 , 3 and the 5-vertex path P 5 is almost classified. We also prove a number of new hardness results for Colouring on ( 2 P 2 , H ) -free graphs. This enables us to list all graphs H for which the complexity of Colouring is open on ( 2 P 2 , H ) -free graphs and all graphs H for which the complexity of Colouring is open on ( P 5 , H ) -free graphs. In fact we show that these two lists coincide. Moreover, we show that the complexities of Colouring for ( 2 P 2 , H ) -free graphs and for ( P 5 , H ) -free graphs are the same for all known cases.