4 problems

For a graph class $\mathcal{C}$, say that it has bounded merge-width when its merge-width is bounded by a constant. A first-order transduction is an interpretation of graphs from s…

A graph class is χ-bounded if there is a function $f$ such that every graph $G$ in the class satisfies $\chi(G)\leq f(\omega(G))$, where $\chi(G)$ is the chromatic number and…

Let $c$ be a positive integer. For a graph $G$, write $c$-$pw(G)$ for its $c$-pathwidth, $tw(G)$ for its treewidth, and $n$ for the number of vertices of $G$. The c-pathwidth lower…

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…