@inproceedings { ,
title = {Recognizing Graphs Close to Bipartite Graphs},
abstract = {We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n\^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.},
conference = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS).},
doi = {10.4230/lipics.mfcs.2017.70},
note = {EPrint Processing Status: Full text deposited in DRO},
publicationstatus = {Published},
url = {https://durham-repository.worktribe.com/output/1148167},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2017},
author = {Bonamy, M. and Dabrowski, K. K. and Feghali, C. and Johnson, M. and Paulusma, D.}
editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}
}