8 problems

Let $F_k(K_n)$ be the $k$-token graph of the complete graph $K_n$, and let $\operatorname{pw}$ and $\operatorname{tw}$ denote pathwidth and treewidth. Optimal path-decomposition co…

For integers $n$ and $k$ with $1\le k\le n-1$, let $F_k(K_n)$ be the $k$-token graph of the complete graph $K_n$, also known as the Johnson graph. The tree decomposition of this gr…

Let $(G,\ell)$ be an instance of textsc{Induced Matching}, together with a path decomposition of $G$ of width $\operatorname{pw}$. The Strong Exponential Time Hypothesis (SETH) ass…

Let $M$ be a connected matroid with rank function $r$. Its circumference is the maximum size of a circuit of $M$, when $M$ has at least one circuit, and its pathwidth is denoted by…

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…

Let $\mathscr{C}$ be a class of graphs with bounded linear rankwidth. A first-order transduction is a graph interpretation obtained using first-order formulas. The class…

Let $g(H)$ denote the least integer $k$ such that every $k$-connected $H$-minor-free graph has bounded pathwidth. Let $\mathcal{H}_2$ be the class of graphs $H$ with $g(H)\leq 2$,…