55 problems

Cereceda's conjecture. For any $d$-degenerate graph $G$ and $d+2$, the diameter of $$ is $O(n^2)$.

Let $G$ be a $d$-regular balanced bipartite graph on $2n$ vertices, and let $f4d8^{\mathbf{connect}}_{k,\mathrm{reg}}(n)$ denote the minimum-degree threshold for the $k$-switch gra…

Let $G$ be a connected graph with $n$ vertices, and let $L$ be a list-assignment of $G$. Write $\mathcal{C}(G,L)$ for the $L$-recolouring graph and $\widehat{\mathcal{C}}(G,L)$ for…

Let $d\geq 3$. In distance-$d$ independent set reconfiguration, denoted by $\textsc{D}d\textsc{ISR}$, configurations are distance-$d$ independent sets, and under the token-sliding…

Vizing's conjecture. Every equivalence class of $k$-colorings of a line graph contains a minimum coloring, for every choice of $k$.

Mynhardt–Roux's conjecture. For every $n\geq3$, $P_n$ is not an $\operatorname{IR}$-graph, and for every $n\geq5$, $C_n$ is not an $\operatorname{IR}$-graph.

Eulerian flow-connectedness conjecture. The following two claims hold:

Let $G$ be a graph, let $\mathcal{U} = \{U_1, \ldots, U_m\}$ be a partition of $V(G)$, and let $k \ge -1$. Write $\mathbf{Col}(\mathcal{I}(G),\mathcal{U})$ for the colorful complex…

Let $\delta^{\mathbf{no\ iso}}_k(n)$ denote the minimum-degree threshold such that the $k$-switch graph of an $n$-vertex graph, when nonempty, is guaranteed to have positive minimu…

Let $G$ be an $n$-vertex graph, or alternatively a balanced bipartite graph on $2n$ vertices, and let $\mathcal H_2(G)$ be its $2$-switch graph of perfect matchings. Giant-componen…

Let $P$ be a set of $n$ points in the plane in general position. A non-crossing spanning tree on $P$ is a spanning tree with vertex set $P$ whose edges are pairwise non-crossing st…

Typical move-count conjecture. The typical number of moves required for reconfiguration is of order $n^2$.

Three-dimensional reconfiguration conjecture. The double-switch move should suffice to reconfigure any Hamiltonian cycle into any other Hamiltonian cycle in a three-dimensional rec…

Let $G$ be a graph, let $L$ be a list assignment for which $L$-colorings are considered, and let $\mathcal{R}_L(G)$ be the graph whose vertices are the proper $L$-colorings of $G$,…

Dismantling characterization. $\operatorname{Recol}_{\mathbb{M}}(N)$ is trivial if and only if $N$ dismantles to the loop $M^\ell(K_1)$ or the edge $M(K_2)$.

Polynomial mixing-time conjecture. The mixing time of the solitaire Markov chain is polynomial in $n$.

Odd-hole-free recolouring conjecture. All odd-hole-free graphs of maximum degree $\Delta$ and clique number $\omega$ are $k$-recolourable for

Triangle-free recolouring conjecture. Any triangle-free graph $G$ is $k$-recolourable for all

Reed's recolouring conjecture. Any graph $G$ is $k$-recolourable for all

Let $(\mu,k)$ be a spherical profile, meaning profile data for square-tiled surfaces on the sphere. Let $\operatorname{ST}(\mu,k)$ denote the corresponding set of square-tiled surf…

Let $\boldsymbol{\theta}=(\theta_1,\theta_2,\theta_3)$ be the relevant profile data for a square-tiled surface, and let $\theta_4$ be a non-negative integer such that … For an inte…

A square-tiled surface is a combinatorial quadrangulation equipped with the cylinder-shear reconfiguration operation. The associated quadratic differential determines a point in a…

Cambie et al.'s conjecture. If

Cambie et al.'s conjecture. If

Let $\mathcal{G}$ be a natural graph class, and let $k$ be a positive integer. For a graph $G$ with a $k$-assignment $L$, let $\mathcal{C}_L(G)$ be the graph of proper $L$-coloring…