20 problems

Fix $k\in\mathbb{N}$. Let $G$ be a connected graph with treewidth at most $k$. A non-edge $xy\notin E(G)$ is a $k$-ghost-edge if, for every tree decomposition $(T,\mathcal{B})$ of…

Abrishami–Czyżewska–Kluk–Pilipczuk–Pilipczuk–Rzążewski's conjecture. Every graph class with balanced separators consisting of few neighborhoods admits tree-decompositions whose bag…

Bounded-entry tree integer-programming conjecture. The integer program can be solved in polynomial time for constant $d$.

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…

Abrishami et al.'s conjecture. The existence of weighted balanced separators contained in a bounded number of balls of bounded radius implies the existence of a tree-decomposition…

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

Dereniowski–Osula conjecture. The bound on the spread in the stated theorem can be improved so that it depends only on $\deg_G(v)$, rather than on $k$ as well.

The strong spanning-tree decomposition conjecture. There is a function $f$ such that every connected graph $G$ has a tree decomposition $(T,\mathcal{B})$ of width at most…

The spanning-tree decomposition conjecture. There is a function $f$ such that every connected graph $G$ has a tree decomposition $(T,\mathcal{B})$ of width at most…

The tree-decomposition minor conjecture. There is a function $f$ such that every connected graph $G$ has a tree decomposition $(T,\mathcal{B})$ of width at most…

2-balanced double tree decomposition conjecture. Any double tree has a $2$-balanced double tree decomposition.

Let $T$ be a monadically NIP theory, meaning that every expansion of a model of $T$ by unary predicates is NIP. A tree decomposition of a model is understood in the sense used by B…

A graph $G$ is $\preccurlyeq$-ubiquitous if, whenever a graph $\Gamma$ satisfies $nG\preccurlyeq\Gamma$ for every $n\in\mathbb{N}$, it also satisfies $\aleph_0G\preccurlyeq\Gamma$,…

Let $G$ be a graph and let $t$ be an integer. The tree-chromatic number $\mathsf{tree}\textnormal{-}\chi(G)$ is the minimum, over tree-decompositions of $G$, of the maximum chromat…

Let $\underline{X}$ be the input random vector and let $\underline{X}_{{\mathcal M}_i}$ denote the model random vector obtained after $i$ cascade-tree stages. Write…

Chromatic boundedness conjecture. There exists a function $f:\mathbb{N}\to\mathbb{N}$ such that $\chi(G)\leq f(k)$ for every $k\geq 1$ and every graph $G$ admitting a spaghetti tre…

Canonical sequence conjecture. For every graph $G$ there exists a canonical sequence of tree-decompositions $(T_i,\mathcal{V}_i)$ for $1 \leq i \leq n$ of $G$ such that:

Let $G$ be a graph with tree-length $tl(G)$, and let $(T_i,\phi_i)$, $H_i$, $S_i$, $B_k(x_i)$, and property $P_i$ be as in the $(k,\ell)$-Disk Tree algorithm. Suppose that…

Let $G$ be a graph with tree-length $tl(G)$, and let $(k,\ell)$-Disk Tree denote the algorithm described in the paper, with parameters $k$ and $\ell$. Dourisboure–Gavoille's refine…

Let $G$ be a graph, and let $tl(G)$ denote its tree-length. The $k$-disk-tree algorithm is the algorithm that constructs a tree decomposition using parameter $k$. Dourisboure–Gavoi…