3 problems

Fix a positive integer $d$, and let $\mathcal{B}_d$ be the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$. A hereditary class is Pollyanna if every hereditary…

Linear vertex deletion conjecture. There is a constant $c>0$ such that, for every graph $G$ embedded on a surface of Euler genus $g$, at most $cg$ vertices can be removed so that t…

Large-edgewidth boxicity conjecture. There exists an integer $e_\Sigma$ such that every graph $G$ embeddable on $\Sigma$ with edgewidth at least $e_\Sigma$ has boxicity at most thr…