Skip to main content

Research Repository

Advanced Search

Recognizing Graphs Close to Bipartite Graphs

Bonamy, M.; Dabrowski, K. K.; Feghali, C.; Johnson, M.; Paulusma, D.

Recognizing Graphs Close to Bipartite Graphs Thumbnail


Authors

M. Bonamy

K. K. Dabrowski

C. Feghali



Contributors

Kim G. Larsen
Editor

Hans L. Bodlaender
Editor

Jean-Francois Raskin
Editor

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.

Citation

Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Recognizing Graphs Close to Bipartite Graphs. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.70

Conference Name 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS).
Conference Location Aalborg, Denmark
Start Date Aug 21, 2017
End Date Aug 25, 2017
Acceptance Date Jun 12, 2017
Online Publication Date Jun 22, 2017
Publication Date Dec 1, 2017
Deposit Date Jul 2, 2017
Publicly Available Date Mar 28, 2024
Series Title LIPIcs–Leibniz International Proceedings in Informatics
Series Number 83
Series ISSN 1868-8969
Book Title 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.
DOI https://doi.org/10.4230/lipics.mfcs.2017.70
Public URL https://durham-repository.worktribe.com/output/1148167

Files





You might also like



Downloadable Citations