Bonamy, Marthe ;
Dabrowski, Konrad K. ;
Feghali, Carl ;
Johnson, Matthew ;
Paulusma, Daniël
Recognizing Graphs Close to Bipartite Graphs
Abstract
We continue research into a wellstudied 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 kdegenerate graphs. The problem is known to be polynomialtime solvable if k=0 (bipartite graphs) and NPcomplete if k=1 (nearbipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomialtime solvability for graphs of diameter 2. We show that recognizing nearbipartite graphs of diameter 3 is NPcomplete 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 kcolourings of a graph of bounded maximum degree.
BibTeX  Entry
@InProceedings{bonamy_et_al:LIPIcs:2017:8074,
author = {Marthe Bonamy and Konrad K. Dabrowski and Carl Feghali and Matthew Johnson and Dani{\"e}l Paulusma},
title = {{Recognizing Graphs Close to Bipartite Graphs}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {70:170:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8074},
URN = {urn:nbn:de:0030drops80740},
doi = {10.4230/LIPIcs.MFCS.2017.70},
annote = {Keywords: degenerate graphs, nearbipartite graphs, reconfiguration graphs}
}
01.12.2017
Keywords: 

degenerate graphs, nearbipartite graphs, reconfiguration graphs 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

01.12.2017 