Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration. Issue 1 (24th May 2021)

• Record Type: Journal Article
• Authors: Bonamy, Marthe; Dabrowski, Konrad K.; Feghali, Carl; Johnson, Matthew; Paulusma, Daniël
• Is Part Of: Journal of graph theory. Volume 98:Issue 1(2021)
• Page Start: 81
• Page End: 109
• Publication Date: 2021-05-24
• Subjects: degenerate graphs -- near‐bipartite graphs -- reconfiguration graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22683
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We continue research into a well‐studied family of problems that ask whether the vertices of a given 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 consider the case where G is the class of k ‐degenerate graphs. This problem is known to be polynomial‐time solvable if k = 0 (recognition of bipartite graphs), but NP ‐complete if k = 1 (near‐bipartite graphs) even for graphs of maximum degree 4. Yang and Yuan showed that the k = 1 case is polynomial‐time solvable for graphs of maximum degree 3. This also follows from a result of Catlin and Lai. We study the general k ≥ 1 case for n ‐vertex graphs of maximum degree k + 2 . We show how to find A and B in O ( n ) time for k = 1, and in O ( n 2 ) time for k ≥ 2 . Together, these results provide an algorithmic version of a result of Catlin and also provide an algorithmic version of a generalization of Brook's Theorem, proved by Borodin et al. and Matamala. The results also enable us to solve an open problem of Feghali et al. For a given graph G and positive integer ℓ, the vertex colouring reconfiguration graph of G has as its vertex set the set of ℓ ‐colourings of G and contains an edge between each pair of colourings that differ on exactly on vertex. We complete the complexity classification of the problem of finding a path in the reconfiguration graph between two given ℓ ‐colourings of a given graph of maximum degree k .