26 problems

Higashitani–Matsumoto conjecture.

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 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…

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)$.

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 $\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…

Let $S$ be a point set in general position. A plane spanning path on $S$ is a noncrossing straight-line spanning path, and the flip graph has these paths as vertices, with adjacenc…

Blowup recolorability conjecture. Every blowup of $G$ is recolorable if and only if every induced subgraph of $G$ is recolorable.

Let $G$ be a graph. A $4$-To-$3$ instance asks whether a proper $4$-coloring of $G$ can be transformed into a proper $3$-coloring by repeatedly recoloring one vertex while maintain…

Let $G$ be a graph and let $k$ be an integer with $k\geq 4$. A $k$-coloring of $G$ is a proper vertex coloring using colors from a set of $k$ colors, and $k$-Mixing asks whether an…

Let $M$ be a matroid of rank $r$, and let $X_1$ and $X_2$ be disjoint bases. The exchange distance of two basis sequences is the minimum number of symmetric exchanges needed to tra…

Revised Kempe-class conjecture. If $G$ is a $(k-1)$-colorable $B+E_\ell$ graph with $k\geq 4$ and

Let $D$ be a digraph on $n$ vertices, and let $\delta^*_{\min}(D)$ denote its min-degeneracy. Let ${\cal D}_k(D)$ be the graph whose vertices are the $k$-dicolourings of $D$, with…

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…

Regular Cereceda's Conjecture. If $k=d+2$, then

Bonamy–Bousquet–Feghali–Johnson conjecture. If $G=(V,E)$ is $d$-degenerate and $k>d$ is an integer, then $\mathcal{K}_k(G)$ has diameter

Let $K_{s,t}$ be the complete bipartite graph with part sizes $s$ and $t$, and let $\mathscr{PD}^{TAR}(K_{s,t})$ denote its power domination reconfiguration graph under token addit…

Let $G_{p,q}$ denote the graph used as the target for $(p,q)$-colourings, and let the textsc{G{p,q}}-Mixing problem ask whether the reconfiguration graph of $(p,q)$-colourings of a…

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.

Bonsma–Cereceda's conjecture. For $k\geq\operatorname{col}(G)+1$,