29 problems

Conjecture on diagonal-flip stabilization. The only surfaces $S$ for which

Exponential lower-bound conjecture. There is an exponential lower bound for the runtime of that algorithm.

Forest reconfiguration conjecture. A forest can always be reconfigured on any non-orientable surface.

Esperet et al.'s flow reconfiguration conjecture. For each graph $G$ and each positive integer $k$,

Let $G$ be a graph, let $\operatorname{diam}(G)$ denote its inversion diameter, and let $\Delta(G)$ denote its maximum degree. Havet et al.'s inversion diameter conjecture. Every g…

Let $G$ be a $d$-dimensional orthotope grid graph with $d\geq3$, and let $H$ and $K$ be two distinct Hamiltonian paths of $G$. A backbite move is the endpoint-relocation move defin…

Let $G$ be a 3-dimensional cuboid grid graph, or 3-orthotope, and let $H$ and $K$ be two distinct Hamiltonian cycles of $G$. A double-switch move and a switch move are the local mo…

Let $G$ be an $m\times n$ grid graph, and let $H$ and $K$ be two distinct disjoint cycle covers of $G$. A double-switch move is the local move defined in the source; for a general…

Let $G$ be an $m\times n$ grid graph, and let $H$ and $K$ be two distinct Hamiltonian cycles of $G$. A flip and a transpose are the local moves defined in the source. Flip-and-tran…

Let $G$ be an $m\times n$ grid graph embedded on a cylinder or torus, and let $H$ and $K$ be two distinct Hamiltonian cycles of $G$. A valid quadruple-switch move is the four-switc…

Let $G$ be a polyomino, and let $H$ and $K$ be two distinct Hamiltonian cycles of $G$. A valid quadruple-switch move consists of four successive switches whose final subgraph is ag…

Let $\mathcal{H}(m,n)$ be the set of Hamiltonian cycles of the $m\times n$ grid graph and let $\mathcal{H}_{\mathrm{res}}(m,n)$ be the subset of resistant cycles. Rarity conjecture…

Let $G$ be an $m \times n$ grid graph, and let $H$ and $K$ be Hamiltonian cycles of $G$. Tightness conjecture. There exists a constant $\alpha\in(0,1)$ such that, for all sufficien…

Let $G$ be an $m \times n$ grid graph and let $H$ be a Hamiltonian cycle of $G$. A resistant cycle is one whose reconfiguration requires the extremal order of moves discussed in th…

Let $G$ be an $m \times n$ grid graph and let $H$ be a Hamiltonian cycle of $G$. The proved worst-case upper bound is less than $n^2m$ moves for complete reconfiguration. Typical-m…

Let $G$ be a graph, and let $\mathcal{F}(G,\mathbb{Z}_2^k)$ denote the reconfiguration graph of nowhere-zero $\mathbb{Z}_2^k$-flows. A nowhere-zero $\mathbb{Z}_2^k$-flow…

Let $G$ be a graph, let $\mathbb{Z}_{4k}$ be the cyclic group of integers modulo $4k$, and let $\mathcal{F}(G,\mathbb{Z}_{4k})$ denote the reconfiguration graph of nowhere-zero…

Let $G$ be a graph, and let $\mathcal{F}(G,A)$ denote its reconfiguration graph whose vertices are nowhere-zero $A$-flows, with adjacency given by changing flow values only on a cy…

Let $G$ be a graph, and let $\mathcal{F}(G,k)$ denote its reconfiguration graph whose vertices are nowhere-zero $k$-flows, with adjacency given by changing flow values only on a cy…

Let $G$ be a graph from a nowhere dense class, and let $k$ be the parameter bounding the size of the connected dominating sets in the token-jumping connected dominating set reconfi…

Let $G$ be a graph. For each positive integer $k$, let $\mathcal{C}_k(G)$ be the graph whose vertices are the proper $k$-colourings of $G$, with two colourings adjacent when they d…

Let $T$ be a tree and let $G$ be a graph. The skew token exchange reconfiguration graph of $G$ is denoted by $\mathcal{Z}^{\mathrm{TE}}_-(G)$. Non-realizability conjecture. No tree…

The non-optimal edge-coloring equivalence conjecture. Any two non-optimal colorings are equivalent.

The $(\Delta(G)+2)$-edge-coloring equivalence conjecture. All $(\Delta(G)+2)$-edge-colorings of a graph $G$ are equivalent.

Path extremizer conjecture. For every $k\ge 2$ and every $n$, there exists a graph $G$ on $n$ vertices maximizing $D(n,k)$ such that