13 problems

Let $k\in\mathbb{N}$, let $G$ be a connected graph with $tw(G)\leq k$, and let $xy\in E(G^c)$. A $k$-ghost-edge is a nonedge $xy$ such that every tree decomposition…

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…

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

Let $G$ be a graph. For a graph relation $\vartriangleleft$, say that $G$ is $\vartriangleleft$-ubiquitous if, whenever a graph $\Gamma$ satisfies … for every $n\in\mathbb{N}$, it…

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…