Bonamy, M. and Dabrowski, K.K. and Feghali, C. and Johnson, M. and Paulusma, D. (2017) 'Recognizing graphs close to bipartite graphs.', in 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, p. 70. LIPIcs–Leibniz International Proceedings in Informatics. (83).
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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution.
Download PDF (587Kb)
|Publisher Web site:||https://doi.org/10.4230/LIPIcs.MFCS.2017.70|
|Publisher statement:||© Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson and Daniël Paulusma; licensed under Creative Commons License CC-BY|
|Date accepted:||12 June 2017|
|Date deposited:||03 July 2017|
|Date of first online publication:||22 June 2017|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|