12 problems

Let $n\geq 5$, and let $\operatorname{K}(n,2)$ be the Kneser graph whose vertices are the $2$-element subsets of $[n]$, with two vertices adjacent when the corresponding subsets ar…

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…

Let $G$ be a graph with maximum degree $\Delta$, and let $\operatorname{box}(G)$ denote its boxicity. Chandran et al.'s conjecture. The boxicity of a graph is $O(\Delta)$. The pape…

Chandran–Sivadasan conjecture. For every integer $k\geq 1$, there exists a $k$-tree $G$ such that

Let $\mathcal{F}$ be a family of $n$ axis-parallel boxes in the plane or in $\mathbf{R}^d$ for $d>2$, and let $G=G(\mathcal{F})$ be its intersection graph. If the maximum number of…

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…

Eppstein–Jampani conjecture. Every locally planar graph has boxicity at most $3$.

Let $G$ be a graph with maximum degree $\Delta(G)$, and let $\pi(G)$ denote its pairwise suitability number. Linear upper-bound conjecture. One has … The paper presents this as a c…

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…

Esperet's conjectures. For every graph $G$, both

Otachi–Okamoto–Yamazaki's conjecture. Every chordal bipartite graph has boxicity at most $2$.

Linear boxicity conjecture for random regular graphs. For almost all $k$-regular graphs,