5 problems

Chi-boundedness conjecture. For any two integers $k,c\in\mathbb{N}$ there exists an integer $r$ such that every graph with induced matching treewidth at most $k$ and clique number…

Let a graph class have bounded induced matching treewidth, meaning that the induced matching treewidth of every graph in the class is bounded by a common constant. Fix a monadic se…

Tree-independence conjecture. For any two integers $k,t\in\mathbb{N}$ there exists an integer $r$ such that every graph with induced matching treewidth at most $k$ and no induced s…

Bounded-treewidth induced subgraph conjecture. In polynomial time one can find a maximum-weight induced subgraph of $G$ with treewidth at most $r$.

CMSO₂ meta-theorem. For every fixed $k,r$ and a $\mathsf{CMSO}_2$ formula $\psi$, the $(r,\psi)$-textsc{MWIS} problem can be solved in polynomial time for graphs with induced match…