Recognizing Graphs Close to Bipartite Graphs

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

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, August). Recognizing Graphs Close to Bipartite Graphs. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS).
• 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: Jul 3, 2017
• 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