12 problems

A graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree at most $d$. For a graph $G$, a $({\rm degree}+d)$-list assignment assigns each vertex $v$ a list…

Let $G$ be a graph on $n$ vertices with $m$ edges, and let $\alpha_1(G)$ denote the order of a largest induced $1$-degenerate subgraph of $G$, equivalently a largest induced forest…

For a graph $G$ with $n$ vertices and genus $g$, let $\alpha_1(G)$ denote the order of a largest induced $1$-degenerate subgraph of $G$, equivalently a largest induced forest. Half…

Let $\alpha_d(k)$ denote the infimum, over $k$-degenerate graphs, of the ratio of the order of a largest induced $d$-degenerate subgraph to the number of vertices. Induced-degenera…

Strong $\delta$-conjecture for $\nu$. For any graph $G$,

Let $G$ be a graph, and let $d$ be a nonnegative integer such that $G$ is $d$-degenerate, meaning that every subgraph of $G$ has a vertex of degree at most $d$. Let $\triangle$-fre…

Let $\operatorname{tw}(G)$ denote the treewidth of $G$. A graph is $2$-degenerate if every induced subgraph has a vertex of degree at most $2$. The complete, complete-bipartite, or…

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…

Polynomial degeneracy conjecture for graphs excluding subdivisions. For every graph $H$, every $H$-subdivision-free graph $G$ that does not contain $K_{\ell,\ell}$ as a subgraph ha…

2-degeneracy conjecture. If $G\in\mathcal{G}_s^s$, then $G$ is $2$-degenerate; that is, every non-empty induced subgraph of $G$ has a vertex of degree at most $2$.

Let $G$ be a planar graph. To delete a vertex means to remove it and its incident edges. To collect a vertex means to remove it when its current degree is at most $4$; a set is col…