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

Let $\mathscr C$ be a class of tree-ordered weakly sparse graphs (TOWS graphs). A dense analogue of a weakly sparse class property is obtained by requiring every weakly sparse tran…

Sintiari–Trotignon conjecture. For every $t$ there exists a constant $c_t$ such that every $n$-vertex $K_t$-free and even-hole-free graph has treewidth at most

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…

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…

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…

Linear-bound conjecture. There exists an integer $g(c)$ such that

For a positive integer $t$, an (even hole, $K_t$)-free graph is a graph containing neither an even hole nor a clique $K_t$ as an induced subgraph. Logarithmic treewidth conjecture.…

Dynamic programming conjecture. A dynamic programming approach similar to the one used on trees can be used on graphs with treewidth $2$.

Bounded distance-number conjecture. The distance number of every graph with treewidth at most $k$ and degree at most $\ell$ is bounded by

A graph property is CMSOL-definable if it can be expressed by a sentence in counting monadic second-order logic, and it is recognizable if it can be recognized by a finite-state tr…

Let $G$ be a random graph sampled from $\mathcal{G}(n,c/n)$, where $c>1$, and consider the threshold for $G$ to have tree-width linear in $n$. Gao's conjecture. The threshold for h…

Chandran–Sivadasan conjecture. For every integer $k\geq 1$, there exists a $k$-tree $G$ such that

Let $G_0=K_3$. For $k\geq1$, let $G_k$ be the planar $3$-tree obtained by adding a $3$-simplicial vertex onto the vertex set of each face of $G_{k-1}$. Let…

Let ${\mathcal{T}}_k$ be the class of graphs of treewidth at most $k$, and let ${\textup{\textsf{bt}}_{}(G)}$ denote the book thickness of a graph $G$. Ganley and Heath proved that…

Lima, Milanič, Muršič, Okrasa, Rzążewski, and Štorgel's conjecture. For every fixed $r$ and formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS can be solved in polynomial time…

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 $\mathcal{C}$ be a class of graphs with bounded treewidth. Bounded-treewidth rainbow separability conjecture. The class $\mathcal{C}$ is rainbow separable. This conjecture asks…

Induced grid-minor conjecture for sparse graph classes. Sparse graph classes should admit induced grid-minor theorems.