2026-07-24T00:34:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8074 2024-03-06T10:40:58Z ddc:004 open_access

Recognizing Graphs Close to Bipartite Graphs Bonamy, Marthe Dabrowski, Konrad K. Feghali, Carl Johnson, Matthew Paulusma, Daniël degenerate graphs near-bipartite graphs reconfiguration graphs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marthe Bonamy and Konrad K. Dabrowski and Carl Feghali and Matthew Johnson and Daniël Paulusma 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.70 urn:nbn:de:0030-drops-80740 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.70 eng https://creativecommons.org/licenses/by/3.0/legalcode