17 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…

Let $G$ be a planar graph on $n$ vertices, and let $\alpha_2(G)$ denote the order of a largest induced $2$-degenerate subgraph of $G$. Gu–Kierstead–Oum–Qi–Zhu conjecture. Every pla…

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

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

Erdős's conjecture. All even cycles $C_{2t}$ with $t\geq 3$ are $g$-degenerate.

Let $d$ be sufficiently large, and let $G$ be a triangle-free graph. Write $\chi_f(G)$ for its fractional chromatic number, and say that $G$ is $d$-degenerate if every subgraph of…

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…

A graph is $d$-degenerate if every subgraph has minimum degree at most $d$, and let $r(H;2)$ denote the two-colour Ramsey number of a graph $H$. Burr–Erdős conjecture. For every fi…

Let $D$ be a digraph on $n$ vertices, let $\mathcal{D}_k(D)$ be the graph whose vertices are the $k$-dicolourings of $D$, and let $\delta^*_{\min}(D)$ denote the min-degeneracy of…

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…