Reconfiguration of list L(2,1) L ( 2 , 1 ) -labelings in a graph
For an integer k?0 k ? 0 , suppose that each vertex v of a graph G  has a set C(v)?{0,1,,k} C ( v ) ? { 0 , 1 ,  , k } of labels, called a list of v . A list L(2,1) L ( 2 , 1 ) -labeling of G  is an assignment of a label in C(v) C ( v ) to each vertex v of G  such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2,1) L ( 2 , 1 ) -labeling of a graph into another list L(2,1) L ( 2 , 1 ) -labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2,1) L ( 2 , 1 ) -labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and k?6 k ? 6 . In contrast, we then show that the problem can be solved in linear time for general graphs if k?4 k ? 4 . We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2,1) L ( 2 , 1 ) -labelings of a tree can be transformed into each other.
1 ) graph algorithm l(2 1) l ( 2 1 ) -labeling l(2 1 ) l(2 1 ) l ( 2 pspace-complete reachability on solution space