## 1 Introduction

In this note, we introduce a counter-example for Proposition 6 of [1] 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 [2]. (Duc A. Hoang (me) and Ryuhei Uehara are co-authors in both publications.)

## 2 The problem

Let $I,J$ be two given independent sets of a graph $G$. 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 $G$ starting from $I$ and ending with $J$ 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 $I\stackrel{\mathit{G}}{\leftrightsquigarrow}J$. In [1], 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 $2$-connected subgraphs) are cliques.

## 3 Proposition 6 and its counter-example

Let $I$ be an independent set of a graph $G$. Let $W\subseteq V(G)$ and assume that $I\cap W\ne \mathrm{\varnothing}$. We say that a token $t$ placed at some vertex $u\in I\cap W$ is $(G,I,W)$-confined if for every $J$ such that $I\stackrel{\mathit{G}}{\leftrightsquigarrow}J$, $t$ is always placed at some vertex of $W$. In other words, $t$ can only be slid along edges of $G[W]$. Let $H$ be an induced subgraph of $G$. $H$ is called $(G,I)$-confined if $I\cap V(H)$ is a maximum independent set of $H$ and all tokens in $I\cap V(H)$ are $(G,I,V(H))$-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 $I$ be an independent set of a block graph $G$. Let $w\mathrm{\in}V\mathrm{(}G\mathrm{)}$. Assume that no block of $G$ containing $w$ is $\mathrm{(}G\mathrm{,}I\mathrm{)}$-confined. If there exists some vertex $x\mathrm{\in}N{}_{G}\mathrm{[}w\mathrm{]}\mathrm{\cap}I$ such that the token $t{}_{x}$ placed at $x$ is $\mathrm{(}G\mathrm{,}I\mathrm{,}N{}_{G}\mathrm{[}w\mathrm{]}\mathrm{)}$-confined, then $x$ is unique. Consequently, there must be some independent set $J$ such that $I\stackrel{\mathit{G}}{\mathrm{\leftrightsquigarrow}}J$ and $N{}_{G}\mathrm{[}w\mathrm{]}\mathrm{\cap}J\mathrm{=}\mathrm{\{}x\mathrm{\}}$. Moreover, let $H$ be the graph obtained from $G$ by turning $N{}_{G}\mathrm{[}w\mathrm{]}$ into a clique, called $B{}_{w}$. Then $t{}_{x}$ is $\mathrm{(}G\mathrm{,}J\mathrm{,}N{}_{G}\mathrm{[}w\mathrm{]}\mathrm{)}$-confined if and only if $B{}_{w}$ is $\mathrm{(}H\mathrm{,}J\mathrm{)}$-confined.

The statement Moreover, let $H$ be the graph obtained from $G$ by turning $N{}_{G}\mathrm{[}w\mathrm{]}$ into a clique, called $B{}_{w}$. Then $t{}_{x}$ is $\mathrm{(}G\mathrm{,}J\mathrm{,}N{}_{G}\mathrm{[}w\mathrm{]}\mathrm{)}$-confined if and only if $B{}_{w}$ is $\mathrm{(}H\mathrm{,}J\mathrm{)}$-confined is indeed not correct.

Figure 1 illustrates a counter-example of this statement. Here, the block $B{}_{w}$ of $H$ (containing $t{}_{x}$) is $(H,J)$-confined but $t{}_{x}$ is not $(G,J,N{}_{G}[w])$-confined. The red arrows in Figure 1 describes a way of moving $t{}_{x}$ out of $N{}_{G}[w]$. (The numbers inside red circles indicate the order of performing the steps described by the red arrows.)

## 4 Progress on resolving the issue

So far, we have not been able to resolve this issue.

## References

- [1] (2017) Sliding Tokens on Block Graphs. In Proceedings of WALCOM 2017, LNCS, Vol. 10167, pp. 460–471. External Links: Document Cited by: §1, §2, Proposition 1.
- [2] (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: Document Cited by: §1.