{'fraction_non_alphanumeric': 0.07170072739868376, 'fraction_numerical': 0.013249047454104606, 'mean_word_length': 3.3047962226640157, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs

We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives precise analyses of the problem with respect to pathwidth.


Introduction
Graph coloring is one of the most fundamental research topics in the field of theoretical computer science. Let C = {1, 2, . . . , k} be the set of k colors. A (proper) k-coloring of a graph G = (V, E) is a mapping f : V → C such that f (v) = f (w) for every edge vw ∈ E. In list coloring, each vertex v ∈ V has a set L(v) ⊆ C of colors, called the list of v. Then, a k-coloring f of G is called a k-list coloring of G if f (v) ∈ L(v) holds for every vertex v ∈ V . Figure 1(b) illustrates four k-list colorings of the same graph G with the same list L depicted in Fig. 1(a); the color assigned to each vertex is attached to the vertex. Clearly, a k-coloring of G is a k-list coloring of G for which L(v) = C holds for every vertex v of G, and hence k-list coloring is a generalization of k-coloring.
Graph coloring has several practical applications, such as in scheduling, frequency assignments. For example, in the frequency assignment problem, each vertex corresponds to a base station and each edge represents the physical proximity and hence the two corresponding base stations have the high potential of interference. Each color represents a channel of a particular frequency, and we wish to find an assignment of channels to the base stations without any interference. Furthermore, in list coloring, each base station can have a list of channels that can be assigned to it.

Our problem
However, a practical issue in channel assignments requires that the formulation should be considered in more dynamic situations. One can imagine a variety of practical scenarios where a k-list coloring (e.g., representing a feasible channel assignment) needs to be transformed (to use a newly found better solution or to satisfy new side constraints) by individual color changes (keeping the network functionality and preventing the need for any coordination) while maintaining feasibility (so that the users receive service even during the reassignment).
In this paper, we thus study the following problem: Suppose that we are given two k-list colorings of a graph G (e.g., the leftmost and rightmost ones in Fig. 1(b)), and we are asked whether we can transform one into the other via k-list colorings of G such that each differs from the previous one in only one vertex color assignment. We call this decision problem the k-list coloring reconfiguration problem. For the particular instance of Fig. 1(b), the answer is "yes," as illustrated in Fig. 1(b), where the vertex whose color assignment was changed from the previous one is depicted by a black circle.

Known and related results
Recently, similar settings of problems have been extensively studied in the framework of reconfiguration problems [13], which arise when we wish to find a stepby-step transformation between two feasible solutions of a problem such that all intermediate solutions are also feasible. This reconfiguration framework has been applied to several well-studied combinatorial problems, including satisfiability [11,21], independent set [6,12,13,20,22], set cover, matching [13], shortest path [3,4,19], list edge-coloring [14,16], list L(2, 1)-labeling [15], and so on.
In particular, the k-coloring reconfiguration problem (i.e., k-list coloring reconfiguration in which L(v) = C holds for every vertex v) is one of the most well-studied reconfiguration problems, from the various viewpoints [1,2,5,7,10,18,25], as follows.
Bonsma and Cereceda [5] proved that k-coloring reconfiguration is PSPACE-complete for k ≥ 4; they also proved that k-list coloring reconfiguration is PSPACE-complete, even for bipartite planar graphs and k = 4. On the other hand, Cereceda et al. [10] proved that k-coloring reconfiguration is solvable for any graph in polynomial time for the case where 1 ≤ k ≤ 3.
Then, some sufficient conditions have been proposed so that any pair of kcolorings of a graph has a desired transformation. Cereceda [9] gave a sufficient condition with respect to the number k of colors: if k is at least the treewidth of a graph G plus two, then there is a desired transformation between any pair of k-colorings of G; the length of the transformation (i.e., the number of recoloring steps) is estimated by Bonamy and Bousquet [2]. Bonamy et al. [1] gave a sufficient condition with respect to graph structures: for example, chordal graphs and chordal bipartite graphs satisfy their sufficient condition.
Recently, Bonsma et al. [7] and Johnson et al. [18] independently developed a fixed-parameter algorithm to solve k-coloring reconfiguration when parameterized by k + ℓ, where k is the number of colors and ℓ is the number of recoloring steps. In contrast, if the problem is parameterized only by ℓ, then it is W[1]-hard [7] and does not admit a polynomial kernelization unless the polynomial hierarchy collapses [18].
In this way, even for the non-list version, only a few results are known from the viewpoint of polynomial-time solvability. Furthermore, as far as we known, no algorithmic result has been obtained for the list version.

Our contribution
In this paper, we study the k-list coloring reconfiguration problem from the viewpoint of graph classes, especially pathwidth of graphs. (The definition of pathwidth will be given in Section 2. ) We first show that the problem remains PSPACE-complete even for graphs with pathwidth two. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives precise analyses of the problem with respect to pathwidth.
Indeed, our reduction for the PSPACE-completeness proof constructs a bipartite series-parallel graph (whose treewidth is two), which is a bipartite planar graph. We note that the problem of finding one k-list coloring of a given graph can be solved in polynomial time for bounded treewidth graphs (and hence for bounded pathwidth graphs) [17]. However, our proof shows that the reconfiguration variant is PSPACE-complete even if treewidth and pathwidth are two. Furthermore, as a byproduct, our reduction can be extended for threshold graphs.

Preliminaries
We assume without loss of generality that graphs are simple and connected. Let G = (V, E) be a graph with vertex set V and edge set E; we sometimes denote by V (G) and E(G) the vertex set and edge set of G, respectively. For a vertex v in G, we denote by We now define the notion of pathwidth [24]. A path-decomposition of a graph G is a sequence of subsets X i of vertices in G such that (1) (2) for each vw ∈ E(G), there is at least one subset X i with v, w ∈ X i ; and (3) for any three indices p, q, r such that p ≤ q ≤ r, X p ∩ X r ⊆ X q .
The width of a path-decomposition is defined as max i |X i | − 1, and the pathwidth of G is the minimum t such that G has a path-decomposition of width t.
To develop our algorithm in Section 4, it is important to notice that every connected graph of pathwidth one is a caterpillar [23]. A caterpillar will be defined in Section 4, but an example can be found in Fig. 4.
For a graph G with a list L, we define the reconfiguration graph R L G as follows: each node of R L G corresponds to a k-list coloring of G, and two nodes of R L G are joined by an edge if their corresponding k-list colorings f and f ′ satisfy , that is, f ′ can be obtained from f by changing the color assignment of a single vertex v. We will refer to a node of R L G in order to distinguish it from a vertex of G. Since we have defined k-list colorings as the nodes of R L G , we use graph terms such as adjacency and path for k-list colorings. For notational convenience, we sometimes identify a node of R L G with its corresponding k-list coloring of G if it is clear from the context. Given a graph G with a list L and two k-list colorings f 0 and f r of G, the k-list coloring reconfiguration problem asks whether the reconfiguration graph R L G has a path between the two nodes f 0 and f r .

PSPACE-completeness
In this section, we first prove that the problem is PSPACE-complete even for graphs with pathwidth two. Then, we show in Section 3.3 that the reduction can be extended to proving the PSPACE-completeness of threshold graphs.
A graph is series-parallel if it does not contain a subdivision of a complete graph K 4 on four vertices [8]. Note that series-parallel graphs may have superconstant pathwidth, although their treewidth can be bounded by two. We give the following theorem. Theorem 1. The k-list coloring reconfiguration problem is PSPACEcomplete even for bipartite series-parallel graphs of pathwidth two.
It is known that k-list coloring reconfiguration is in PSPACE [5]. Therefore, as a proof of Theorem 1, we give a polynomial-time reduction from the shortest path rerouting problem [4] (defined in Section 3.1) to our problem for bipartite series-parallel graphs of pathwidth two.

Reconfiguration problem for shortest path
Let H be an unweighted graph, and let s and t be two vertices in H. We call a shortest path in H between s and t simply an S-path in H. Note that, since H is unweighted, an S-path indicates a path between s and t having the minimum number of edges. We say that two S-paths P and P ′ in H are adjacent if they differ in exactly one vertex, that is, |V (P ′ ) \ V (P )| = 1 and |V (P ) \ V (P ′ )| = 1 hold. Given two S-paths P 0 and P r in H, the shortest path rerouting problem asks whether there exists a sequence P = P 0 , P 1 , . . . , P ℓ of S-paths  such that P ℓ = P r , and P i−1 and P i are adjacent for each i = 1, 2, . . . , ℓ. This problem is known to be PSPACE-complete [4].
To construct our reduction, we introduce some terms. Let d be the number of edges of an S-path in a graph H. For two vertices v and w in H, we denote by dist(v, w) the number of edges of a shortest path in H between v and w; then dist(s, t) = d. For each i ∈ {0, 1, . . . , d}, the layer D s,i from s is defined to be the set of all vertices in H that are placed at distance i from s, that is,

Reduction
Given an instance (H, P 0 , P r ) of shortest path rerouting, we construct the corresponding instance (G, L, f 0 , f r ) of k-list coloring reconfiguration.

Construction of G and L.
We first construct the corresponding graph G with a list L. For each i ∈ {1, 2, . . . , d − 1}, let D i = {v i,1 , v i,2 , . . . , v i,q }; and we introduce a vertex u i , called a layer vertex, to G. The list of each layer vertex u i is defined as L(u i ) = {c i,1 , c i,2 , . . . , c i,q }, where each color c i,j in L(u i ) corresponds to the vertex v i,j in D i ; assigning color c i,j represents selecting the vertex v i,j as an S-path in H.
We denote by U layer the set of all layer vertices u 1 , u 2 , . . . , u d−1 in G. In Fig. 2(b), each layer vertex u i is illustrated as a black vertex which is the same shape as the vertices in D i .
We then connect layer vertices in G by forbidden paths of length two, as follows. Let v i,x ∈ D i and v i+1,y ∈ D i+1 be an arbitrary pair of vertices in H such that v i,x v i+1,y ∈ E(H). We introduce a vertex w to G, and join w and each of the two layer vertices u i and u i+1 by an edge. The list L(w) of w consists of two colors c i,x and c i+1,y which correspond to the vertices v i,x and v i+1,y in H, respectively. (See the vertices depicted by white circles in Fig. 2 otherwise there is no color in L(w) that can be assigned to w. This property ensures that every k-list coloring of G corresponds to an S-path in H. Let U forbid be the set of all forbidden vertices, then This completes the construction of G and L. Since Clearly, G is a bipartite series-parallel graph of pathwidth two, whose bipartition consists of U layer and U forbid .
Construction of f 0 and f r .
We now construct two k-list colorings f 0 and f r of G which correspond to S-paths P 0 and P r in H, respectively. For each i ∈ {1, 2, . . . , d−1}, let v i,0 be the vertex in the layer D i passed through by the S-path P 0 ; then we let f 0 (u i ) = c i,0 for each layer vertex u i ∈ U layer . For each (v i,x , v i+1,y )-forbidden vertex w ∈ U forbid , we choose an arbitrary color from c i,x and c i+1,y which is assigned to neither u i nor u i+1 . We note that such an available color always exists, because P 0 has an edge between the two vertices corresponding to the colors f 0 (u i ) and f 0 (u i+1 ), and hence at least one of f 0 (u i ) = c i,x and f 0 (u i+1 ) = c i+1,y holds for each (v i,x , v i+1,y )-forbidden vertex. Similarly, we construct f r . This completes the construction of the corresponding instance (G, L, f 0 , f r ).

Correctness of the reduction.
To show the correctness of this reduction, we give the following lemma.
Proof. We first prove the if-part. Suppose that the reconfiguration graph R L G has a path between the two nodes f 0 and f r . We can classify the recoloring steps into the following two types: (1) recoloring a layer vertex in U layer , and (2) recoloring a forbidden vertex in U forbid . Therefore, the path in R L G can be divided into sub-paths, intermittently at each edge corresponding to a recoloring step of type (1) above; all edges in a sub-path correspond to recoloring steps of type (2) above. Therefore, all nodes in each sub-path correspond to the same S-path in H. Furthermore, any two consecutive sub-paths correspond to two adjacent Spaths (that differ in only one vertex), because the sub-paths are divided by a recoloring step of type (1). Thus, we can construct a sequence of adjacent S-paths that transforms P 0 into P r .
We then prove the only-if-part. Suppose that there exists a sequence P = P 0 , P 1 , . . . , P ℓ of S-paths such that P ℓ = P r , and P j−1 and P j are adjacent for each j = 1, 2, . . . , ℓ. For two adjacent S-paths P j−1 and P j , j ∈ {1, 2, . . . , ℓ}, assume that P j is obtained from Fig. 3(a).) This rerouting step from v i,x to v i,y corresponds to recoloring the layer vertex u i ∈ U layer from the color c i,x to c i,y . (See Fig. 3

(b).)
To do so, if there is a forbidden vertex w ∈ U forbid which is adjacent with u i and receives the color c i,y , we first need to recolor w from c i,y to another color c q,z ∈ L(w) \ {c i,y }, where q ∈ {i − 1, i + 1}. (Note that, since P j−1 corresponds to a feasible k-list coloring of G, no forbidden vertex adjacent with u i receives the color c i,x .) Since w is a forbidden vertex, we know that |L(w)| = 2. Let v q,a be the vertex in the layer D q which is adjacent with v i,x and v i,y in P j−1 and P j , respectively; and hence the layer vertex u q receives the color c q,a . ( Figure 3 illustrates the case where q = i − 1.) Then, since each forbidden vertex is placed only for a pair of vertices in H which is not joined by an edge, we observe that the color c q,z ∈ L(w) \ {c i,y } is different from c q,a . Therefore, we can recolor w from c i,y to another color c q,z without recoloring any other vertices. Since U forbid forms an independent set of G, we can apply this recoloring step to all forbidden vertices independently. Now, any neighbor of u i is colored with neither c i,x nor c i,y , and hence we can recolor u i from c i,x to c i,y . Thus, R L G has a path between f 0 and f r which corresponds to P. ⊓ ⊔

Threshold graphs
In this subsection, we extend our reduction in Section 3.2 to threshold graphs. A graph G is threshold if there exist a real number s and a mapping ω : where R is the set of all real numbers.
Theorem 2. The k-list coloring reconfiguration problem is PSPACEcomplete even for threshold graphs.
Proof. We modify the graph G constructed in Section 3.2, as follows: join all pairs of vertices in U layer , and join each vertex in U forbid with all vertices in U layer . Let G ′ be the resulting graph, then G[U layer ] forms a clique and G[U forbid ] forms an independent set. Notice that G ′ is a threshold graph; set the threshold s = 1, and the mapping ω(v) = 1 for each layer vertex v ∈ U layer and ω(u) = 0 for each forbidden vertex u ∈ U forbid . Consider any pair of vertices u and v such that uv ∈ E(G ′ ) \ E(G), that is, they are joined by a new edge for constructing G ′ from G. Then, by the construction in Section 3.2, the two lists L(u) and L(v) contain no color in common. Therefore, adding new edges to G does not affect the existence of klist coloring: more formally, any k-list coloring of G is a k-list coloring of G ′ , and vice versa. Thus, by Lemma 1, an instance (H, P 0 , P r ) of shortest path rerouting is a yes-instance if and only if (G ′ , L, f 0 , f r ) is a yes-instance.

Algorithm for Graphs with Pathwidth One
In contrast to Theorem 1, we give the following theorem in this section.
Theorem 3. The k-list coloring reconfiguration problem can be solved in polynomial time for graphs with pathwidth one.
As a proof of Theorem 3, we give such an algorithm. However, since every connected graph of pathwidth one is a caterpillar [23], it suffices to develop a polynomial-time algorithm for caterpillars.
A caterpillar G is a tree whose vertex set V (G) can be partitioned into two subset V S and V L such that G[V S ] forms a path and each vertex in V L is incident to exactly one vertex in V S . We may assume without loss of generality that the two endpoints of the path G[V S ] are of degree one in the whole graph G. (See v 1 and v 10 in Fig. 4.) We call each vertex in V S a spine vertex of G, and each vertex in V L a leaf of G.
We assume that all vertices in G are ordered as v 1 , v 2 , . . . , v n by the breadthfirst search starting with the endpoint (degree-1 vertex) of the spine path G[V S ] with the priority to leaves; that is, when we visit a spine vertex v, we first visit all leaves of v and then visit the unvisited spine vertex. (See Fig. 4 Fig. 4. A caterpillar G and its vertex ordering, where the subgraph surrounded by a dotted rectangle corresponds to G8.
We can restrict the length of each list without loss of generality, as follows. Note that the following lemma holds for any graph.
Proof. If |L(v)| = 1 for a vertex v ∈ V (G ′ ), then any k-list coloring f ′ of G ′ assigns the same color c ∈ L(v) to v. Therefore, f ′ never assigns c to any neighbor u of v. We can thus delete v from G ′ and set L(u) := L(u) \ {c} for all neighbors u of v in G ′ . Clearly, this modification does not affect the reconfigurability (i.e., the existence or non-existence of a path in the reconfiguration graph). If , we simply delete v from G ′ without any modification of lists; let G be the resulting graph. Let f be any k-list coloring of G, and consider a recoloring step for a neighbor u of v from the current color c = f (u) to another color c ′ . If c ′ is not assigned to v in G ′ , we can directly recolor u from c to c ′ . Thus, suppose that c ′ is assigned to v in G ′ . Then, since |L(v)| ≥ d(v) + 2, there is at least one color c * ∈ L(v) which is not c ′ and is not assigned to any of d(v) neighbors of v by f . Therefore, we first recolor v from c ′ to c * , and then recolor u from c to c ′ . In this way, any recoloring step in G can be simulated in G ′ , and hence the modification does not affect the reconfigurability.
Thus, we can obtain an instance such that 2 ≤ |L(v)| ≤ d(v)+1 holds for each vertex v without affecting the reconfigurability. Clearly, the modified instance can be constructed in polynomial time.
⊓ ⊔ Therefore, in the remainder of this section, we assume that G is a (connected) caterpillar and 2 ≤ |L(v)| ≤ d(v) + 1 holds for every vertex v ∈ V (G). In particular, |L(v)| = 2 for every leaf v of G.

Idea and definitions
The main idea of our algorithm is to extend techniques developed for shortest path rerouting [3], and apply them to k-list coloring reconfiguration for caterpillars. Our algorithm employs a dynamic programming method based on the vertex ordering v 1 , v 2 , . . . , v n of G.
For each i ∈ {1, 2, . . . , n}, let R L Gi be the reconfiguration graph for the subgraph G i and the list L. Then, R L Gi contains all k-list colorings of G i as its nodes. Our algorithm efficiently constructs R L Gi for each i = 1, 2, . . . , n, in this order. However, of course, the number of nodes in R L Gi cannot be bounded by a polynomial size in general. We thus use the property that the vertex v i+1 (will be added to G i ) is adjacent with only the spine vertex sp(i) in G i+1 ; and we "encode" the reconfiguration graph R L Gi into a polynomial size with keeping the information of (1) the color assigned to sp(i), and (2) the connectivity of nodes in R L Gi . Before explaining the encoding methods, we first note that it suffices to focus on only one connected component in R L Gi which contains the restriction of f 0 , where the restriction of a k-list coloring f of a graph G to a subgraph G ′ is a k-list coloring g of G ′ such that g(v) = f (v) hold for all vertices v ∈ V (G ′ ). For notational convenience, we denote by f [V i ] the restriction of a k-list coloring f of a caterpillar G to its subgraph G i . Then, we have the following lemma. We now partition the nodes of R 0 i into several subsets with respect to (1) the color assigned to sp(i), and (2) the connectivity of nodes in R 0 i . For two nodes g and g ′ of R 0 i with g(sp(i)) = g ′ (sp(i)), we write g ∼ sp(i) g ′ if g can be reconfigured into g ′ without recoloring the color assigned to the vertex sp(i), that is, R 0 i has a path g 1 , g 2 , . . . , g ℓ such that g 1 = g, g ℓ = g ′ , and g j (sp(i)) = g(sp(i)) = g ′ (sp(i)) holds for every j ∈ {1, 2, . . . , ℓ}. Since the adjacency relation on k-list colorings is symmetric (i.e., R i is an undirected graph), it is easy to see that ∼ sp(i) is an equivalence relation. Thus, the node set of R 0 i can be uniquely partitioned by the relation ∼ sp(i) . We denote by G 0 i the partition of the node set of R 0 i into equivalence classes with respect to ∼ sp(i) .
We finally define our dynamic programming table. For each subgraph G i , i ∈ {1, 2, . . . , n}, our algorithm keeps track of four information (H i , col i , ini i , tar i ), defined as follows.
-The encoding graph H i of R 0 i which can be obtained from R 0 i by contracting each node set in G 0 i into a single node. (See Fig. 5 as an example.) We will refer to an e-node of H i in order to distinguish it from a node of R 0 i . (Thus, each node refers to a k-list coloring of G i , and each e-node refers to a set of k-list colorings of G i .) For each e-node x ∈ V (H i ), we denote by Φ i (x) the set of all nodes in R 0 i that were contracted into x. (Note that we do not compute Φ i (x), but use it only for definitions and proofs.) -The color col i (x) ∈ L(sp(i)) for each e-node x ∈ V (H i ), which is assigned to sp(i) in common by the nodes (i.e., k-list colorings of G i ) in Φ i (x). - To prove Theorem 3, we give a polynomial-time algorithm which computes (H i , col i , ini i , tar i ) for each subgraph G i , i ∈ {1, 2, . . . , n}, by means of dynamic programming. Then, the problem can be solved as in the following lemma. Proof. Since H n contains a node x such that tar n (x) = 1, we have f r [V n ] = f r ∈ Φ n (x). Recall that H n is the encoding graph of R 0 n which contains the k-list coloring f 0 of G as a node. Since Φ n (x) ⊆ V (R 0 n ), the lemma clearly follows. ⊓ ⊔

Algorithm
As the initialization, we first consider the case where i = 1, that is, we compute (H 1 , col 1 , ini 1 , tar 1 ). (See Fig. 6(d) as an example.) Note that G 1 consists of a  single vertex v 1 , and recall that v 1 is a spine vertex of degree one. By Lemma 2 we then have |L(v 1 )| = 2. Therefore, the reconfiguration graph R 1 is a complete graph on |L(v 1 )| = 2 nodes such that each node corresponds to a k-list coloring of G 1 which assigns a distinct color to the vertex sp(1) = v 1 . Since R 1 is complete and contains the node f 0 [V 1 ], we have R 0 1 = R 1 . Furthermore, H 1 = R 0 1 since all nodes in R 0 1 assign distinct colors in L(v 1 ) to sp(1) = v 1 . Then, for each e-node x of H 1 corresponding to the set consisting of a single k-list coloring g of G 1 , we set We define an encoding graphĤ . Then, we have the following lemma. We now defineî ni i (x) andt ar i (x) for each e-node x inĤ ′ i , as follows: contains an e-node y with ini i−1 (y) = 1; 0 otherwise, EN(x) contains an e-node y with tar i−1 (y) = 1; 0 otherwise. LetĤ i be the connected component ofĤ ′ i that contains the e-node x such thatî ni i (x) = 1. Then, we have the following lemma.

Running time
We now estimate the running time of our algorithm in Section 4.2. The following is the key lemma for the estimation.
In particular, |V (H n )| = O(n), where n is the number of vertices in G.
By Lemma 7 each encoding graph H i is of size O(n) for each i ∈ {1, 2, . . . , n}. Therefore, our algorithm clearly runs in polynomial time.
This completes the proof of Theorem 3. ⊓ ⊔

Concluding Remarks
In this paper, we gave precise analyses of the k-list coloring reconfiguration problem with respect to pathwidth: the problem is solvable in polynomial time for graphs with pathwidth one, while it is PSPACE-complete for graphs with pathwidth two. Very recently, Wrochna [25] gave another proof for the PSPACE-completeness of k-list coloring reconfiguration for graphs with pathwidth two. His reduction is constructed from a PSPACE-complete problem, called H-Word Reachability.

A Proofs Omitted from Section 4
We first introduce some notation.
For i ≥ 2, let h be any node (i.e., a k-list coloring of G i ) in the reconfiguration graph R i−1 . Recall that the vertex v i is adjacent with only the spine vertex sp(i − 1) in G i . Let c be any color in L(v i ) \ {f (sp(i − 1))}. Then, we say that h can be extended by c to a k-list coloring g of G i such that g(v i ) = c and g(v) = h(v) for all vertices v ∈ V i−1 ; we simply denote such an extension by h + c = g. Note that g is a node in R i .
For any e-node y in the encoding graph

A.1 Proof of Lemma 5
In this subsection, we prove Lemma 5. Therefore, suppose that we have already Proof. Let g be any node in Φ i (x) ⊆ V (R 0 i ). Then, by Lemma 3 the node g[V i−1 ] is contained in R 0 i−1 , and hence there exists an e-nodex in H i−1 such that . Thus, the e-nodex is contained inĤ ′ i , too. Therefore, we prove that . Let g ′ be any node in Φ i (x). Then, g ∼ sp(i) g ′ , and hence R 0 i contains a path g 1 , g 2 , . . . , g ℓ such that g 1 = g, g ℓ = g ′ and g j (sp(i)) = g(sp(i)) = g ′ (sp(i)) for all j ∈ {1, 2, . . . , ℓ}. Thus, we can obtain a path in which the spine vertex sp(i) always receives the same color g(sp(i)) = g ′ (sp(i)); i . If g(v i ) = c, we add one more adjacent node h ℓ + c to the last. Since h 1 + g(v i ) = g and h ℓ + c = g ′′ , we thus have g ∼ sp(i) g ′′ and hence g ′′ ∈ Φ i (x).
⊓ ⊔ By Lemma 8 we may identify each e-node x in H i with the corresponding e-nodex inĤ ′ i . We then prove the following lemma.
Lemma 9. Let x and y be two e-nodes in H i , and letx andŷ be two e-nodes inĤ ′ i corresponding to x and y, respectively. Then,xŷ ∈ E( Proof. We first prove the only-if-part. Suppose thatxŷ ∈ E(H c1 i−1 ); it is symmetric for the other case wherexŷ ∈ E(H c2 i−1 ). Then, there exist two adjacent nodes h x ∈ Φ i−1 (x) and h y ∈ Φ i−1 (ŷ) such that h x (sp(i − 1)) = c 1 and h y (sp(i − 1)) = c 1 . Therefore, by Lemma 8 we have h x + c 1 ∈ Φ i (x) and h y + c 1 ∈ Φ i (y). Note that, sincex =ŷ, we know that only the spine vertex sp(i − 1) = sp(i) is recolored between h x and h y . Thus, h x + c 1 and h y + c 1 are adjacent in R 0 i , and hence we have xy ∈ E(H i ). We then prove the if-part. Since xy ∈ E(H i ), there exist two adjacent nodes g x ∈ Φ i (x) and g y ∈ Φ i (y) in R 0 i . Since x = y, only the spine vertex sp(i) is recolored between g x and g y , and hence g x (v i ) = g y (v i ). Therefore, g x [V i−1 ] and g y [V i−1 ] are adjacent. We assume that c 1 = g x (v i ) = g y (v i ) without loss of generality. Then, since v i and sp(i) are adjacent, g x (sp(i)) = c 1 and g y (sp(i)) = c 1 . By Lemma 8 we have g We now prove the following lemma. Therefore, to show H i =Ĥ i , by Lemma 9 it suffices to prove that there exists no edge xŷ ∈ E(Ĥ i ) which joins two e-nodes Suppose for a contradiction that there exists such an edge xŷ ∈ E(Ĥ i ). By the construction, xŷ ∈ E(H c1 i−1 ) ∪ E(H c2 i−1 ); we may assume that xŷ ∈ E(H c1 i−1 ) without loss of generality. Then, there exist two adjacent nodes h x ∈ Φ i−1 (x) and hŷ ∈ Φ i−1 (ŷ) such that h x (sp(i − 1)) = c 1 and hŷ(sp(i − 1)) = c 1 . Therefore h x and hŷ can be extended by c 1 , and h x + c 1 ∈ Φ i (x) and hŷ + c 1 ∈ Φ i (ŷ) are adjacent in R 0 i . By Lemma 8 we then haveŷ ∈ V (H i ); this contradicts the assumption thatŷ ∈ V (Ĥ i ) \ V (H i ).
⊓ ⊔ Finally, we show the following lemma.
Then, the lemma follows immediately from Lemma 8.

⊓ ⊔
This completes the proof of Lemma 5.

A.2 Proof of Lemma 6
In this subsection, we prove Lemma 6. Therefore, suppose that we have already computed (H i−1 , col i−1 , ini i−1 , tar i−1 ) for i ≥ 2, and assume that v i ∈ V S . We first prove that V (H i ) ⊆ V (Ĥ ′ i ) holds, as in the following lemma. Lemma 12. Let x be any e-node in H i with col i (x) = c. Then, there exists exactly one connected component H in Proof. Let g be any node in Φ i (x) ⊆ V (R 0 i ). Then, by Lemma 3 the node g[V i−1 ] is contained in R 0 i−1 , and hence there exists an e-node z in H i−1 such that g[V i−1 ] ∈ Φ i−1 (z). Since sp(i) = sp(i − 1) and sp(i) is adjacent with sp(i − 1), the assumption col i (x) = c implies that g(sp(i)) = c and hence g(sp(i − 1)) = c. Therefore, we have col i−1 (z) = c, and hence H c i−1 has exactly one connected component H that contains z. We thus prove that Let g ′ be any node in Φ i (x). Then, g ′ (sp(i)) = c and hence it suffices to show that H contains an e-node y such that g ′ [V i−1 ] ∈ Φ i−1 (y). Since g ∼ sp(i) g ′ , there exists a path g 1 , g 2 , . . . , g ℓ in R 0 i such that g 1 = g, g ℓ = g ′ and g j (sp(i)) = g(sp(i)) = g ′ (sp(i)) = c for all j ∈ {1, 2, . . . , ℓ}. Since sp(i) is adjacent with sp(i− 1), g j (sp(i − 1)) = c holds for all j ∈ {1, 2, . . . , ℓ}. Therefore, there exists a con- Thus, H contains an e-node y such that g ′ [V i−1 ] ∈ Φ i−1 (y). Then, we have g ′ ∈ {Φ i−1 (y) ⊕ c : y ∈ V (H)}.
Conversely, let g ′′ be any node in {Φ i−1 (y) ⊕ c : y ∈ V (H)}. Since H is connected, the subgraph of R 0 i−1 induced by {Φ i−1 (y) : y ∈ V (H)} is connected, too. Then, the induced subgraph contains a path h 1 , h 2 , . . . , h ℓ such that h 1 = g[V i−1 ] and h ℓ = g ′′ [V i−1 ]. Furthermore, since H is a connected component in H c i−1 , we know that h j (sp(i − 1)) = c for all nodes h j , j ∈ {1, 2, . . . , ℓ}. Therefore, we can extend each node h j by c, and obtain a path h 1 + c, h 2 + c, . . . , h ℓ + c . Since h 1 + c = g and h ℓ + c = g ′′ , we thus have which satisfies Lemma 12. Then, we can identify the e-node x in H i with the e-nodex inĤ ′ i such that EN(x) = V (H x ). We then prove the following lemma.
Lemma 13. Let x and y be two e-nodes in H i , and letx andŷ be two e-nodes inĤ ′ i corresponding to x and y, respectively. Then, EN(x) ∩ EN(ŷ) = ∅ if and only if xy ∈ E(H i ).
Proof. We first prove the only-if-part. Suppose that the set EN(x) ∩ EN(ŷ) contains an e-node a in H i−1 . Choose an arbitrary node h ∈ Φ i−1 (a), then two nodes h + col i (x) ∈ Φ i (x) and h + col i (y) ∈ Φ i (y) are adjacent in R 0 i . Thus, xy ∈ E(H i ).
We then prove the if-part. Suppose that xy ∈ E(H i ), then there exist two adjacent nodes g x ∈ Φ i (x) and g y ∈ Φ i (y) in R 0 i . Since g x and g y are adjacent and col i (x) = col i (y), we know that g x [V i−1 ] = g y [V i−1 ]. By Lemma 12, there exists an e-node a ∈ EN(x) such that g ⊓ ⊔ By Lemmas 12 and 13, we have H i ⊆Ĥ ′ i and col i =ĉol i . We now prove the following lemma. Proof. We prove only ini i =î ni i ; it is similar to prove tar i =t ar i . Let x be any e-node in H i such that ini i (x) = 1.
Conversely, letx be any e-node inĤ ′ i such thatî ni i (x) = 1. Then, EN(x) contains an e-node y such that ⊓ ⊔ Finally, we show following lemma.
Proof. Recall that H i consists of a single connected component which contains the e-node z such that f 0 [V i ] ∈ Φ i (z). By Lemma 13 H i is contained in one connected component ofĤ ′ i as a subgraph, and the connected component contains an e-nodeẑ such that f 0 [V i ] ∈ Φ i (ẑ). By Lemma 14 we haveî ni i (ẑ) = 1, and hence the connected component is indeedĤ i . We thus have H i ⊆Ĥ i . Therefore, to show H i =Ĥ i , by Lemma 13 it suffices to prove that there exists no edge xŷ ∈ E(Ĥ i ) which joins two e-nodes x ∈ V (H i ) andŷ ∈ V (Ĥ i ) \ V (H i ). Suppose for a contradiction that there exists such an edge xŷ ∈ E(Ĥ i ). Then, the set EN(x) ∩ EN(ŷ) contains an e-node z. Choose an arbitrary node h ∈ Φ i−1 (z), then two nodes h + col i (x) and h + col i (ŷ) are adjacent in R 0 i . Then, h + col i (ŷ) ∈ z ′ ∈EN(ŷ) (Φ i−1 (z ′ ) ⊕ col i (ŷ)). By Lemma 12 the corresponding e-node y should be contained in H i ; this contradicts the assumption thatŷ ∈ V (Ĥ i ) \ V (H i ). ⊓ ⊔ This completes the proof of Lemma 6.

A.3 Proof of Lemma 7
In this subsection, we prove Lemma 7. Since |V (Ĥ i )| ≤ |V (Ĥ ′ i )| holds, it suffices to prove the following inequality: for each index i ∈ {1, 2, . . . , n}, Consider the case where v i is a leaf. Then, V (Ĥ ′ i ) = V (H i−1 ), and hence Eq. (1) clearly holds. In the remainder of this subsection, we thus consider the case where v i is a spine vertex.
For a graph G = (V, E), we denote by cc(G) the number of connected components in G. For a connected graph G, that is, cc(G) = 1, we denote by T G any spanning tree of G. Since E(T G ) ⊆ E(G), we clearly have the following proposition. We now apply Case (B) of our algorithm to any spanning tree T Hi−1 of H i−1 , instead of applying the operation to H i−1 . LetĤ T i be the obtained encoding graph, instead ofĤ ′ i . Then, we have the following lemma.