Skip to main content

Research Repository

Advanced Search

Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration

Bonamy, M; Dabrowski, K.K; Feghali, C; Johnson, M; Paulusma, D

Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration Thumbnail


M Bonamy

K.K Dabrowski

C Feghali


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 [DM, 2006] 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 [DM, 1995]. 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 [JCTB, 1979] and also provide an algorithmic version of a generalization of Brook’s Theorem, proved by Borodin, Kostochka and Toft [DM, 2000] and Matamala [JGT, 2007]. The results also enable us to solve an open problem of Feghali et al. [JGT, 2016]. 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.


Bonamy, M., Dabrowski, K., Feghali, C., Johnson, M., & Paulusma, D. (2021). Recognizing Graphs Close to Bipartite Graphs with an Application to Colouring Reconfiguration. Journal of Graph Theory, 98(1), 81-109.

Journal Article Type Article
Acceptance Date Apr 3, 2021
Online Publication Date May 24, 2021
Publication Date 2021-09
Deposit Date Apr 7, 2021
Publicly Available Date Aug 6, 2021
Journal Journal of Graph Theory
Print ISSN 0364-9024
Electronic ISSN 1097-0118
Publisher Wiley
Peer Reviewed Peer Reviewed
Volume 98
Issue 1
Pages 81-109
Public URL
Publisher URL
Related Public URLs


Published Journal Article (1.4 Mb)

Publisher Licence URL

Copyright Statement
© 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC

This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.

You might also like

Downloadable Citations