2017/07/31 by Bonamy, Marthe, Dabrowski, Konrad K., Feghali, Carl +2
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1707.09817
We continue research into a well-studied family of problems that ask whether 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 \cal G. We let \cal G be the class of k-degenerate graphs. This 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 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 consider graphs of maximum degree k+2 on n vertices. We show how to find A and B in O(n) time for k=1, and in O(n2) 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, which was proven in a more general way by Borodin, Kostochka and Toft [DM, 2000] and Matamala [JGT, 2007]. Moreover, the two results enable us to complete the complexity classification of an open problem of Feghali et al. [JGT, 2016]: finding a path in the vertex colouring reconfiguration graph between two given ℓ-colourings of a graph of maximum degree k.