11 problems

CMSO-fragment conjecture.

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 $d$ be a positive integer. For a graph $G$, write $tw(G)$ for its treewidth, $d$-$pw(G)$ for its $d$-pathwidth, and $n$ for the number of vertices of $G$. The treewidth lower-b…

Let $G$ be a graph, and let the nonlinear parameter be the branch-decomposition analogue of lu-mim width described in the source. Let Structural Deterministic DNNFs and more genera…

Let $G$ range over graphs on $n$ vertices. The lsim width and lu-mim width are the graph parameters referred to respectively as the former and the latter in the source. Separation…

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 $G$ be a graph and let $k$ be a positive integer. A subdivision of a complete binary tree of height $k$ is obtained from a complete binary tree of height $k$ by subdividing edg…

Directed spaghetti treewidth is a graph width parameter; fixed-parameter tractability means that, for parameter $k$, the problem of deciding whether a graph has directed spaghetti…

Let $\Phi$ be a uniformly monotone property, and let $\min(\Phi)$ denote its class of minimal graphs. Vertex-cover number measures the minimum size of a vertex set meeting every ed…