17 problems

Albertson–Berman's conjecture.

Let $D_{3}^{n}$ be a planar digraph with $n$ vertices and directed girth $3$, and let ${\rm fvs}(D_{3}^{n})$ denote its minimum feedback vertex set size. Harutyunyan's conjecture.…

Dross–Montassier–Pinlou conjecture. Every planar graph $G$ of girth at least $g$ satisfies

Goemans–Williamson's conjecture.

Akiyama–Watanabe–Albertson–Hass conjecture. Every bipartite planar graph $G$ satisfies

Low-density normal-set conjecture. Every plane digraph $G$ admits a normal set of cycles with low density and of size $fvs(G)$.

The minimum-energy conjecture.

For any integer $k\ge 2$, let $f(k)$ be the supremum of ${\rm fvs}(D)/|V(D)|$ over all orgraphs $D$ with maximum degree at most $k$, where ${\rm fvs}(D)$ denotes the minimum feedba…

For any integer $k\ge 2$, let $f(k)$ be the supremum of ${\rm fvs}(D)/|V(D)|$ over all orgraphs $D$ with maximum degree at most $k$, where ${\rm fvs}(D)$ denotes the minimum feedba…

Younger’s conjecture. For every directed graph $D$, there exists a function $f$ such that, if $D$ does not contain $k$ disjoint cycles, then $D$ has a feedback vertex set of size a…

Let $k$ be the degeneracy of a digraph, let $n$ be a positive integer, and write $f$ for the size of a minimum feedback vertex set. The paper conjectures that there is an…

Let $k$ be an even degeneracy bound, and let $G$ be an $n$-vertex graph of degeneracy $k$. Write $f$ for the size of a minimum feedback vertex set of $G$. There is an…

Planar packing conjecture. There exists a packing of $g-1$ disjoint feedback vertex sets in $D$.

Higher-girth packing conjecture. There exists a packing of $g$ pairwise disjoint feedback vertex sets in $D$. Equivalently, $D$ can be vertex $g$-coloured such that every directed…

A feedback vertex set of a graph $G$ is a set $S\subseteq V(G)$ such that $G-S$ is a forest. Let $\phi(G)$ denote the minimum size of a feedback vertex set of $G$. The girth of a g…

Feedback vertex set conjecture for prescribed girth. There exists a feedback vertex set $S$ of $G$ satisfying

Paley digraph conjecture. The tournaments $T$ maximizing