81 problems

Let $\mathcal{G}$ be a hereditary class of graphs. A class has bounded tree-independence number if there is a constant $c\in\mathbb{N}$ such that every graph in the class admits a…

Let a graph have finite tree-width if its tree-width is finite, and consider the minor relation on graphs. Finite-tree-width well-quasi-ordering conjecture. The graphs of finite tr…

Fixed-radius coarse separator strengthening. For every $k,r\in\mathbb{N}$, there exists $k'\in\mathbb{N}$ such that if $G$ admits $(k,r)$-balanced separators, then $G$ admits a…

Let $H$ be a graph, let ${\mathrm{tw}}(H)$ denote its tree-width, and let $M_H(n)$ denote the maximum running time of the $H$-process. Tree-width two conjecture. Every graph $H$ wi…

Let $\mathcal{G}$ be a hereditary graph class. A graph is $2$-degenerate if every induced subgraph has a vertex of degree at most $2$, and $\mathcal{G}$ is…

Let $p,q\geqslant 1$ be integers. Define $\ell(p,q)$ to be the minimum integer such that every graph $G$ with treewidth at least $\ell(p,q)$ contains pairwise disjoint connected su…

For a graph $G$, let $\operatorname{tw}(G)$ denote its treewidth. A graph is even-hole-free if it has no induced cycle of even length at least four, and the diamond is the graph on…

Gartland and Lokshtanov's conjecture. For every fixed $r$ and CMSO$_2$ formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS and $\operatorname{lcol}(3)$ can be solved in polynomi…

Let $H$ be a finite graph, and write $f_H(r)$ for its growth function, namely the maximum number of vertices in a ball of radius $r$. For graphs $G_1,\dots,G_k$, let…

Abrishami–Czyżewska–Kluk–Pilipczuk–Pilipczuk–Rzążewski's conjecture. For every $k,r\in\mathbb{N}$, there exist $k',r'\in\mathbb{N}$ such that if $G$ admits $(k,r)$-balanced separat…

Weak knitwork immersion conjecture. The class $\mathbf{T}(k,d,\Delta,\ell;\Omega)$ is well-quasi-ordered by $\Omega$-knitwork immersion.

Treewidth-bounded immersion conjecture. The class of Eulerian digraphs of treewidth at most $k$ is well-quasi-ordered by immersion.

Let $\mathcal{F}$ be a finite class of graphs. A graph is $\mathcal{F}$-free if it has no induced subgraph isomorphic to any member of $\mathcal{F}$. The class of all $\mathcal{F}$…

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…

Let $G$ be a graph, let $k$ be a nonnegative integer, and let $\operatorname{bn}(G)$ denote the basis number of $G$. Treewidth-linear basis number conjecture. Every graph $G$ of tr…

Let $W_{t\times t}$ be the $t$-by-$t$ hexagonal grid and let $K_{t,t}$ be the complete bipartite graph with both sides of the bipartition of size $t$. For a positive integer $t$, l…

Let $G$ be a string graph drawn in a surface of fixed Euler genus $g$, and let $\Delta$ be the maximum degree of $G$. Polynomial row-treewidth conjecture. The row treewidth of $G$…

Let $\mathcal{G}$ be a graph class. For graph parameters $\rho$ and $\omega$, say that $\mathcal{G}$ is $(\rho,\omega)$-bounded when bounded clique number in $\mathcal{G}$ implies…

Let $\mathcal{G}$ be a hereditary graph class. A graph $H$ is $H$-free in $\mathcal{G}$ when graphs in the relevant subclass have no induced subgraph isomorphic to $H$. The class…

Induced-minor-free product structure conjecture. There is a function $f\colon \mathbb{N}\to\mathbb{N}$ such that every $H$-induced-minor-free graph $G$ with maximum degree at most…

Trotignon's conjecture. For all $r,t\in\mathbb{N}$, there exists $c=c(r,t)\in\mathbb{N}$ such that for every graph $G$, if $G$ does not contain $W_{t \times t}$ or $K_{t,t}$ as an…

Georgakopoulos's coarse grid minor conjecture. For every planar graph $H$, there exist $k,q\in\mathbb{N}$ such that every $H$-induced-minor-free graph is $q$-quasi-isometric to a g…

Let a k-tree be a graph obtained from a complete graph on $k+1$ vertices by repeatedly adding a vertex adjacent to all vertices of an existing $k$-clique. An odd coloring of a grap…

Let $G$ be a graph, and say that $G$ excludes a graph as an asymptotic minor if there is an integer $k$ such that the graph is not an asymptotic minor of $G$. Georgakopoulos–Papaso…

A family of unbounded treewidth is a family of graphs whose treewidth is unbounded, and it is essential when its hereditary closure is a minimal hereditary class of unbounded treew…