9 problems

An elimination forest $F$ for a graph $G=(V,E)$ is a rooted forest on $V$ such that every edge of $G$ joins an ancestor and a descendant in $F$. The treedepth $\text{td}(G)$ is the…

For integers $t\geqslant 2$ and $k\geqslant 2$, define … Here, $\operatorname{td}(G)$ is the treedepth of $G$, $\operatorname{tdtwo}(G)$ is its 2-treedepth, and $P_t$ denotes the p…

Let $F$ be a graph with at least two cycles. A graph is $F$-subgraph-free if it contains no subgraph isomorphic to $F$, and let $\mathcal{C}$ denote the class of $F$-subgraph-free…

Let $r\geq 4$. A graph is $C_{2r}$-subgraph-free if it contains no subgraph isomorphic to the cycle $C_{2r}$. The diameter of a graph is the maximum distance between two vertices.…

Let $G$ be a graph, let $\operatorname{td}(G)$ denote its treedepth, and let $\operatorname{lc}(G)$ denote its linear chromatic number. Kun–O'Brien–Pilipczuk–Sullivan's conjecture.…

Kun–O'Brien–et al. conjecture. For any graph $G$,

Let $G$ be a graph, let $p$ be its pathwidth, and let $\ell$ be a positive integer. A path of order $2^\ell$ is a path with $2^\ell$ vertices. Pathwidth–treedepth conjecture. Every…

For $d\in\mathbb{N}$, a graph $G$ is a minimal obstruction for treedepth $d$ if $\mathsf{td}(G)>d$ but $\mathsf{td}(G-v)\le d$ for every vertex $v\in V(G)$. Dvořák et al.'s treedep…

Let $G$ be a pattern graph. For each positive integer $n$, let $\mathrm{SUB}(G)$ denote the Boolean function on inputs encoding an $n$-vertex host graph $H$ whose vertices are colo…