Search

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(n2) 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. [ABSTRACT FROM AUTHOR]

For a graph G and a , b ∈ V ( G ) , the shortest path reconfiguration graph of G with respect to a and b is denoted by S ( G , a , b ) . The vertex set of S ( G , a , b ) is the set of all shortest paths between a and b in G . Two vertices in V ( S ( G , a , b ) ) are adjacent, if their corresponding paths in G differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice. [ABSTRACT FROM AUTHOR]

The $$k$$ -colouring reconfiguration problem asks whether, for a given graph $$G$$ , two proper $$k$$ -colourings $$\alpha $$ and $$\beta $$ of $$G$$ , and a positive integer $$\ell $$ , there exists a sequence of at most $$\ell +1$$ proper $$k$$ -colourings of $$G$$ which starts with $$\alpha $$ and ends with $$\beta $$ and where successive colourings in the sequence differ on exactly one vertex of $$G$$ . We give a complete picture of the parameterized complexity of the $$k$$ -colouring reconfiguration problem for each fixed $$k$$ when parameterized by $$\ell $$ . First we show that the $$k$$ -colouring reconfiguration problem is polynomial-time solvable for $$k=3$$ , settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all $$k \ge 4$$ , we show that the $$k$$ -colouring reconfiguration problem, when parameterized by $$\ell $$ , is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses. [ABSTRACT FROM AUTHOR]