English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We continue research into a well-studied family of problems that ask whetherthe vertices of a graph can be partitioned into sets $A$ and~$B$, where $A$ isan 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. Thisproblem is known to be polynomial-time solvable if $k=0$ (bipartite graphs) andNP-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-timesolvable for graphs of maximum degree $3$. This also follows from a result ofCatlin 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(n^2)$ time for $k\geq 2$. Together, these results provide an algorithmicversion of a result of Catlin [JCTB, 1979] and also provide an algorithmicversion of a generalization of Brook's Theorem, which was proven in a moregeneral way by Borodin, Kostochka and Toft [DM, 2000] and Matamala [JGT, 2007].Moreover, the two results enable us to complete the complexity classificationof an open problem of Feghali et al. [JGT, 2016]: finding a path in the vertexcolouring reconfiguration graph between two given $\ell$-colourings of a graphof maximum degree $k$.

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