M. Bonamy
Recognizing Graphs Close to Bipartite Graphs
Bonamy, M.; Dabrowski, K. K.; Feghali, C.; Johnson, M.; Paulusma, D.
Authors
K. K. Dabrowski
C. Feghali
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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
Accepted Conference Proceeding
(601 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson and Daniël Paulusma; licensed under Creative Commons License CC-BY
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search