80 problems

Square-free grid subgraph conjecture. The grid subgraph $H$ lies in $\mathbf{PGR}$ if and only if $H$ is square-free.

Let $f_d(G)$ denote the minimum number of firefighters needed to contain a fire on a vertex-transitive graph $G$ when firefighters may move at most distance $d$ per turn. Square-gr…

Let $P_n$ denote the finite path grid used to form the three-dimensional grid $P_n\times P_n\times P_n$. Consider an outbreak beginning at one vertex, with one firefighter deployed…

Let $\mathbb{L}^{d}$ be the infinite $d$-dimensional square grid, whose vertices are the points of $\mathbb{R}^{d}$ with integer coordinates, with adjacency defined by Euclidean di…

Let $\mathbb{L}^{d}$ be the infinite $d$-dimensional square grid, whose vertices are the points of $\mathbb{R}^{d}$ with integer coordinates, with adjacency defined by Euclidean di…

Let $G_{m,n}$ be the rectangular grid graph, and let $k$ be a positive integer with $k<n/2$. Reducing the bandwidth of $G_{m,n}$ by $k$ means deleting edges so that the resulting g…

For positive integers $m,n$, let $P_k$ denote the path on $k$ vertices, and let $P_m\times P_n$ be their Cartesian product, with vertices $(g,h)$ and $(g',h')$ adjacent exactly whe…

Periodic perfect-power maximality conjecture. Its spanning-tree count is at most

Perfect-power square-maximality conjecture. Equality should occur only for the $d$-dimensional box $P_n^{\square d}$, up to lattice translation and coordinate permutation.

Let $n\ge 1$ be an integer. Let $S\subset\mathbb{Z}^2$ be a finite set of vertices with $|S|=n^2$, and suppose that the induced subgraph $\mathcal{L}[S]$ of the infinite square-lat…

Let $f: \mathbb{N} \to \mathbb{N}$ be a strictly increasing function, let … for some $d>2$, and let $\mathcal G(f)=(G_n,n\geq 1)$. Write $P(\mathcal G(f))$ for the set of achievabl…

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, 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 $m\geq n\geq 1$ be integers, and let $a$ denote the additional width parameter in a tree-decomposition of the $(n\times m)$-grid whose width is $n+a$. The spread versus width c…

Let $P_m$ be the path graph on $m$ vertices and $C_n$ the cycle graph on $n$ vertices. For a graph $G$, let $\mathrm{f}\mu^{(0)}(G)$ denote its fault-tolerant mutual-visibility num…

Grid-complex equivalence conjecture. For a general grid graph $P_n\times P_m$, vertex decomposability, shellability, and Cohen–Macaulayness of $\Sigma_r(P_n\times P_m)$ are equival…

Let $P_\infty$ be the two-way infinite path with vertex set $\mathbb{Z}$, and let $P_\infty \boxtimes P_\infty$ be the infinite diagonal grid with vertex set…

Let $\alpha_{n,m}$ denote the number of optimal solutions for the $n\times m$ grid in the paper's notation. Let $\texttt{A006318}(k)$ denote the $k$-th Large Schröder number. The L…

Let $\alpha_{n,m}$ denote the number of optimal solutions for the $n\times m$ grid in the paper's notation. In the case of a grid with $2$ rows and $2k+1$ columns, where $k\geq 0$,…

Let $G(n,m)$ be the $n\times m$ grid graph, and let $\gamma_c(G(n,m))$ denote its contamination number. Ainouche–Bouroubi conjecture. For all integers $n,m\geq 0$, … This conjectur…

Grid spread conjecture. Every optimal tree-decomposition of the $n\times n$ grid has very large spread.

Charikar–Liu–Liu–Vuong conjecture. A $1/\operatorname{poly}(n)$ fraction of the $k$-component forests of the grid graph have balanced component sizes.