4 problems

Sparsest-obstruction conjecture. If

Approximation conjecture. For any $\varepsilon>0$, there is a $(2+\varepsilon)$-approximation algorithm for

Let $G$ be a non-edgeless multigraph, let $t\in\mathbb{N}$, and let $\chi_{\textit{OL}}^t(G)$ denote the worst-case number of rounds required for on-line scheduling when each verte…

Let $G$ be a bipartite multigraph with partition classes $A,B$ and maximum degree $d$. Each edge $e$ has an associated integer delay $r(e)$. An edge-colouring is a map…