The double-broom graph $D{}_{r,n,s}$ is the tree obtained from a path $P{}_n=v{}_{1}v{}_2\mathrm{\dots }v{}_n$ by attaching $r$ leaves to $v{}_1$ and $s$ leaves to $v{}_n$, where $r,n,s$ are positive integers. Two independent sets $I,J$ are adjacent under Token Sliding $\mathrm{(}𝖳𝖲\mathrm{)}$ if there exists $u,v\in V(G)$ such that $I\setminus J=\{u\}$, $J\setminus I=\{v\}$, and $uv\in E(G)$. The Token Sliding problem asks whether there is a $𝖳𝖲$-sequence between $I$ and $J$ in $G$, that is, a sequence of independent sets starting with $I$ and ending with $J$ where any two consecutive members are adjacent under $𝖳𝖲$. For a fixed positive integer $k$, the graph $𝖳𝖲{}_k(G)$ contains all size-$k$ independent sets as its vertices/nodes, and two nodes are joined by an edge if their corresponding independent sets are adjacent under $𝖳𝖲$. A graph $G$ is called a $𝖳𝖲{}_k$-graph if there exists a graph $H$ such that $G$ and $𝖳𝖲{}_k(H)$ are isomorphic.

Independent Set Reconfiguration (ISR) is one of the most well-studied problems in the Combinatorial Reconfiguration [12, 5]. Among several variants of ISR, Token Sliding is of particular interest. One of the main reasons is that in Token Sliding one often needs to deal with the situation where a token must make “detours” by “moving away” (and then moving back later) to allow some other token to move [6]. Alternatively, this can be seen as a kind of “bottleneck effect” [3] where a token may not be able to “reach” some vertices which are “far apart” from all tokens because some tokens “block the way”.

Our motivation for Open Problem 1 comes from the following two results that both appeared in 2014.

Indeed, since a graph of bandwidth at most $c$ also has pathwidth and treewidth at most $c$, Theorem 4 holds for graphs of pathwidth/treewidth at most $c$. Moreover, for $c=1$,

Naturally, on graphs of treewidth at most $c$, one may ask what the value of $c$ that separates “hard” from “easy” is. Toward answering this question, a first step is probably to consider $c=2$.

Our motivation for Open Problem 2 and Conjecture 3 comes from [1, 2]. In [1], the authors initiated the study of $𝖳𝖲{}_k(G)$ from a purely graph-theoretic viewpoint. They continued their study in [2] focusing on those that are acyclic. Open Problem 2 involves characterizing general graphs, which seems to be quite challenging and a first step may be to consider well-known graph classes. Toward this direction, in [2], the authors proved a forbidden induced subgraph characterization of a tree $G$ satisfying that $𝖳𝖲{}_k(G)$ is acyclic where $k\in \{2,3\}$ and Conjecture 3, if true, will provide a complete analysis of which trees having acyclic $𝖳𝖲{}_k$-graphs.

For a fixed integer $k\ge 2$, a $k$-path vertex cover of a graph $G$ is a vertex subset $I$ such that any path on $k$ vertices contains at least one member from $I$. Two $k$-path vertex covers are adjacent under Token Sliding ($𝖳𝖲$) if there exists $u,v\in V(G)$ such that $I\setminus J=\{u\}$, $J\setminus I=\{v\}$, and $uv\in E(G)$. The $k$-Path Vertex Cover Reconfiguration under Token Sliding ($k$-PVCR-TS) problem asks if there is a $𝖳𝖲$-sequence between two given $k$-path vertex covers $I$ and $J$ in $G$, that is, a sequence of $k$-path vertex covers starting with $I$ and ending with $J$ where any two consecutive members are adjacent under $𝖳𝖲$.

The $k$-PVCR-TS problem was first introduced in [9]. The complexities of $k$-PVCR-TS and some other variants have been characterized in [9] for some graph classes, including planar and bounded bandwidth graphs, trees, paths, and cycles. However, $k$-PVCR-TS on trees remains open. Our motivation comes from an attempt in [10] to solve this problem for a subclass of trees called caterpillars (i.e., trees obtained by attaching leaves to a central path). Unlike the cases for independent sets, a token may have to make “detours” by “moving closer” (and then moving back later) to allow some other tokens to move.

For a fixed integer $k\ge 1$, a proper $k$-coloring $\alpha$ of a graph $G$ is a function $\alpha :V(G)\to \{1,2,\mathrm{\dots },k\}$ such that for any edge $uv\in E(G)$ we have $\alpha (u)\ne \alpha (v)$. If $G$ has a proper $k$-coloring, we say that it is $k$-colorable. Two proper $k$-colorings $\alpha ,\beta$ are adjacent under Token Swapping if there exist $u,v\in V(G)$ such that $\alpha (u)=\beta (v)$, $\alpha (v)=\beta (u)$, $\alpha (w)=\beta (w)$ for any $w\in V(G)-\{u,v\}$, and $uv\in E(G)$. The $k$-Recoloring under Token Swapping ($k$-RTS) problem asks if there is a sequence of adjacent proper $k$-colorings of $G$ under Token Swapping between two given proper $k$-colorings $\alpha ,\beta$. The graph $𝒞{}_k{}^{RTS}(G)$ takes all proper $k$-colorings of $G$ as its nodes and their adjacency are defined under Token Swapping.

The $k$-RTS problem lies between two of the most well-studied problems in Combinatorial Reconfiguration: Token Swapping [16] and Vertex Recoloring [4]. (See [12, 11] for more details.) RTS was first proposed in [8] where the authors claimed that RTS remains $𝙿𝚂𝙿𝙰𝙲𝙴$-complete on planar graphs and can be solved in polynomial time on paths ($k=3$) and cographs (any $k$). Up to present, their results have not yet been published. The goal of our proposed open problems is to obtain a better understanding on the similarities and differences between $𝒞{}_k{}^{RTS}(G)$ and the well-stuided graph $𝒞{}_k(G)$—the graph whose nodes are proper $k$-colorings of $G$ and two nodes are adjacent if one can be obtained from the other by recoloring exactly one vertex.