In this note, we introduce a counter-example for Proposition 6 of  and the progress of resolving this issue. This example was provided by Mariana Teatini Ribeiro and Vinícius Fernandes dos Santos. This issue has also been announced in . (Duc A. Hoang (me) and Ryuhei Uehara are co-authors in both publications.)
2 The problem
Let be two given independent sets of a graph . Imagine that the vertices of an independent set are viewed as tokens (coins). A token is allowed to move (or slide) from one vertex to one of its neighbors. The Sliding Token problem asks whether there exists a sequence of independent sets of starting from and ending with such that each intermediate member of the sequence is obtained from the previous one by moving a token according to the allowed rule. If such a sequence exists, we write . In , we claimed that this problem is solvable in polynomial time when the input graph is a block graph—a graph whose blocks (i.e., maximal -connected subgraphs) are cliques.
3 Proposition 6 and its counter-example
Let be an independent set of a graph . Let and assume that . We say that a token placed at some vertex is -confined if for every such that , is always placed at some vertex of . In other words, can only be slid along edges of . Let be an induced subgraph of . is called -confined if is a maximum independent set of and all tokens in are -confined.
Mariana Teatini Ribeiro and Vinícius Fernandes dos Santos showed us a counter-example of the following proposition
Proposition 1 ([1, Proposition 6]).
Let be an independent set of a block graph . Let . Assume that no block of containing is -confined. If there exists some vertex such that the token placed at is -confined, then is unique. Consequently, there must be some independent set such that and . Moreover, let be the graph obtained from by turning into a clique, called . Then is -confined if and only if is -confined.
The statement Moreover, let be the graph obtained from by turning into a clique, called . Then is -confined if and only if is -confined is indeed not correct.
4 Progress on resolving the issue
So far, we have not been able to resolve this issue.
-  (2017) Sliding Tokens on Block Graphs. In Proceedings of WALCOM 2017, LNCS, Vol. 10167, pp. 460–471. External Links: Cited by: §1, §2, Proposition 1.
-  (2019) Shortest Reconfiguration Sequence for Sliding Tokens on Spiders. In Proceedings of CIAC 2019, P. Heggernes (Ed.), LNCS, Vol. 11485, pp. 262–273. External Links: Cited by: §1.