Abstract
This document contains a list of open problems that Duc A. Hoang is interested in. It is also available in PDF format. Please get in touch if you have any idea/comment/question/update. You can find (probably more interesting) open problems from the following resources.
 •
 •
 •

•
Graph Theory  Favorite Conjectures and Open Problems  1 (edited by Ralucca Gera, Stephen Hedetniemi, Craig Larson) and Graph Theory  Favorite Conjectures and Open Problems  2 (edited by Ralucca Gera, Teresa W. Haynes, Stephen T. Hedetniemi).
 •
 •
 •
 •
Contents
1 Preliminaries
Unless otherwise noted, all graphs are simple, undirected. We often denote by $P{}_{n},C{}_{n},K{}_{n},K{}_{m,n}$ the path, cycle, complete graph, complete bipartite graph on $n$ vertices, respectively. For two graphs $G,H$, the disjoint union of $G$ and $H$, denoted by $G+H$, is the graph with $V(G+H)=V(G)\cup V(H)$ and $E(G+H)=E(G)\cup E(H)$. For the terminology and notation not defined here, see the textbooks by Diestel [7] or West [14]. For more details on Combinatorial Reconfiguration (https://en.wikipedia.org/wiki/Reconfiguration), see the surveys [13, 12, 11, 5] and the wiki page https://reconf.wikidot.com/.
2 Reconfiguration of Independent Sets under Token Sliding
2.1 Definitions
The doublebroom 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{(}\U0001d5b3\U0001d5b2\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 $\U0001d5b3\U0001d5b2$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 $\U0001d5b3\U0001d5b2$. For a fixed positive integer $k$, the graph $\U0001d5b3\U0001d5b2{}_{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 $\U0001d5b3\U0001d5b2$. A graph $G$ is called a $\U0001d5b3\U0001d5b2{}_{k}$graph if there exists a graph $H$ such that $G$ and $\U0001d5b3\U0001d5b2{}_{k}(H)$ are isomorphic.
2.2 Conjecture/Question
Open Problem 1.
What is the complexity of Token Sliding on outerplanar graphs? And more generally, on seriesparallel graphs ($\mathrm{\equiv}$ graphs of treewidth at most two)?
Open Problem 2.
Let $G$ be a graph. What are necessary and sufficient conditions for $G$ such that $\U0001d5b3\U0001d5b2{}_{\mathrm{2}}\mathrm{(}G\mathrm{)}$ is acyclic?
Conjecture 3.
Let $G$ be a forest. Then $\U0001d5b3\U0001d5b2{}_{k}\mathrm{(}G\mathrm{)}$ is a forest if and only if $G$ is $\mathrm{\{}\mathrm{2}K{}_{\mathrm{2}}\mathrm{+}\mathrm{(}k\mathrm{}\mathrm{2}\mathrm{)}K{}_{\mathrm{1}}\mathrm{,}D{}_{\mathrm{2}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{2}}\mathrm{+}\mathrm{(}k\mathrm{}\mathrm{2}\mathrm{)}K{}_{\mathrm{1}}\mathrm{,}D{}_{\mathrm{2}\mathrm{,}\mathrm{4}\mathrm{,}\mathrm{2}}\mathrm{+}\mathrm{(}k\mathrm{}\mathrm{3}\mathrm{)}K{}_{\mathrm{1}}\mathrm{\}}$free, for some integer $k\mathrm{\ge}\mathrm{4}$.
2.3 Background/Motivation
Independent Set Reconfiguration (ISR) is one of the most wellstudied 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.
Theorem 4 ([15]).
There exists a constant $c$ such that Token Sliding (and two other variants of ISR) is $\U0001d67f\U0001d682\U0001d67f\U0001d670\U0001d672\U0001d674$complete on graphs of bandwidth at most $c$.
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$,
Theorem 5 ([6]).
Token Sliding is in $\U0001d67f$ on trees.
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 $\U0001d5b3\U0001d5b2{}_{k}(G)$ from a purely graphtheoretic 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 wellknown graph classes. Toward this direction, in [2], the authors proved a forbidden induced subgraph characterization of a tree $G$ satisfying that $\U0001d5b3\U0001d5b2{}_{k}(G)$ is acyclic where $k\in \{2,3\}$ and Conjecture 3, if true, will provide a complete analysis of which trees having acyclic $\U0001d5b3\U0001d5b2{}_{k}$graphs.
3 Reconfiguring $k$Path Vertex Covers on Trees under Token Sliding
3.1 Definitions
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 ($\U0001d5b3\U0001d5b2$) 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$PVCRTS) problem asks if there is a $\U0001d5b3\U0001d5b2$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 $\U0001d5b3\U0001d5b2$.
3.2 Conjecture/Question
Open Problem 6.
What is the complexity of $k$PVCRTS on bipartite graphs? Or more restrictedly, on trees?
3.3 Background/Motivation
The $k$PVCRTS problem was first introduced in [9]. The complexities of $k$PVCRTS 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$PVCRTS 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.
4 Recoloring under Token Swapping
4.1 Definitions
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 $\mathcal{C}{}_{k}{}^{RTS}(G)$ takes all proper $k$colorings of $G$ as its nodes and their adjacency are defined under Token Swapping.
4.2 Conjecture/Question
Open Problem 7.
What is the complexity of $k$RTS on trees for some fixed $k\mathrm{\ge}\mathrm{3}$?
Open Problem 8.
What is the smallest value of $k$ such that $\mathcal{C}{}_{k}{}^{RTS}\mathrm{(}G\mathrm{)}$ is connected for some given graph $G$?
Open Problem 9.
What are necessary and sufficient conditions for a $k$colorable graph $G$ such that $\mathcal{C}{}_{k\mathrm{+}\mathrm{1}}{}^{RTS}\mathrm{(}G\mathrm{)}$ is connected?
4.3 Background/Motivation
The $k$RTS problem lies between two of the most wellstudied 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 $\U0001d67f\U0001d682\U0001d67f\U0001d670\U0001d672\U0001d674$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 $\mathcal{C}{}_{k}{}^{RTS}(G)$ and the wellstuided graph $\mathcal{C}{}_{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.
References
 [1] (2022) On Reconfiguration Graph of Independent Sets under Token Sliding. arXiv preprint. External Links: 2203.16861 Cited by: §2.3.
 [2] (2023) A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets. arXiv preprint. External Links: 2301.00317 Cited by: §2.3.
 [3] (2022) Galactic Token Sliding. In Proceedings of ESA 2022, S. Chechik, G. Navarro, E. Rotenberg, and G. Herman (Eds.), LIPIcs, Vol. 244, pp. 15:1–15:14. External Links: Document, 2204.05549 Cited by: §2.3.
 [4] (2007) Finding Paths Between Graph Colourings: PSPACECompleteness and Superpolynomial Distances. In Proceedings of MFCS 2007, LNCS, Vol. 4708, pp. 738–749. External Links: Document Cited by: §4.3.
 [5] (2022) A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems. arXiv preprint. External Links: 2204.10526 Cited by: §1, §2.3.
 [6] (2015) LinearTime Algorithm for Sliding Tokens on Trees. Theoretical Computer Science 600, pp. 132–142. External Links: Document, 1406.6576 Cited by: §2.3, Theorem 5.
 [7] (2017) Graph theory. 5th edition, Graduate Texts in Mathematics, Vol. 173, Springer. External Links: Document Cited by: §1.
 [8] (2019) Color reconfiguration with token swapping. External Links: Link Cited by: §4.3.
 [9] (2022) Reconfiguring $k$Path Vertex Covers. IEICE Transactions on Information and Systems E105D (7), pp. 1258–1272. External Links: Document, 1911.03026 Cited by: §3.3.
 [10] (2022) TSReconfiguration of $k$Path Vertex Covers in Caterpillars for $k\ge 4$. arXiv preprint. External Links: 2203.11667 Cited by: §3.3.
 [11] (2019) Reconfiguration of colourings and dominating sets in graphs. In 50 years of Combinatorics, Graph Theory, and Computing, F. Chung, R. Graham, F. Hoffman, R. C. Mullin, L. Hogben, and D. B. West (Eds.), pp. 171–191. External Links: Document, 2003.05956 Cited by: §1, §4.3.
 [12] (2018) Introduction to reconfiguration. Algorithms 11 (4), pp. 52. External Links: Document Cited by: §1, §2.3, §4.3.
 [13] (2013) The complexity of change. In Surveys in Combinatorics, London Mathematical Society Lecture Note Series, Vol. 409, pp. 127–160. External Links: Document, 1312.2816 Cited by: §1.
 [14] (2001) Introduction to graph theory. 2nd edition, Prentice Hall. Cited by: §1.
 [15] (2018) Reconfiguration in Bounded Bandwidth and Treedepth. Journal of Computer and System Sciences 93, pp. 1–10. External Links: Document, 1405.0847 Cited by: Theorem 4.
 [16] (2015) Swapping Labeled Tokens on Graphs. Theoretical Computer Science 586, pp. 81–94. External Links: Document Cited by: §4.3.