We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Recognizing graphs close to bipartite graphs.

Bonamy, M. and Dabrowski, K.K. and Feghali, C. and Johnson, M. and Paulusma, D. (2017) 'Recognizing graphs close to bipartite graphs.', in 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, p. 70. LIPIcs–Leibniz International Proceedings in Informatics. (83).


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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson and Daniël Paulusma; licensed under Creative Commons License CC-BY
Date accepted:12 June 2017
Date deposited:03 July 2017
Date of first online publication:22 June 2017
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar