11 problems

Let $G$ be a graph of tree-depth $k$, meaning that $k$ is the least number of labels in a vertex ranking of $G$ such that every path joining two vertices with the same label contai…

Let $k\ge 1$. Fix a set $\Gamma$ of colours and consider graphs $G$ whose colour interpretations satisfy $\operatorname{rg}(\gamma^G)\subseteq\Gamma$. For graphs $G,G'$ and a finit…

For a graph class $\mathcal{G}$, let $\chi_{\Delta}(\mathcal{G})$ be the minimum integer $k$ such that, for some integer $d$, every graph in $\mathcal{G}$ is $k$-colourable with de…

Every-critical-graph conjecture. Every critical graph is 1-unique.

Barrus–Sinković conjecture. $G$ has maximum degree at most

Dvořák–Giannopoulou–Thilikos conjecture. $G$ has at most

Nešetřil–Ossona de Mendez conjecture. There exists a constant $t$ such that every planar graph has a vertex coloring with 3 colors in which every monochromatic component has tree-d…

Let $G$ be a critical graph, meaning that it has tree-depth $k$ for some $k$ and every proper minor of $G$ has smaller tree-depth. A graph is 1-unique if, for every vertex $v$ of…

Let $G$ be a critical graph with tree-depth $k$, meaning that $G$ has tree-depth $k$ and every proper minor of $G$ has smaller tree-depth. The maximum-degree conjecture. The maximu…

The maximum-degree conjecture. Every critical graph with tree-depth $k$ has maximum degree at most

The order bound conjecture. Every critical graph with tree-depth $k$ has at most