30 problems

Let $d\text{-degenerate}$ graphs be graphs in which every subgraph has a vertex of degree at most $d$, and let $\chi_o(G)$ denote the oriented chromatic number of a graph $G$. For…

Let $G$ be a $d$-degenerate graph, and let $R_t(G)$ be the graph whose vertices are the proper $t$-colorings of $G$, with two colorings adjacent when they differ on one vertex. The…

Let $d\in\mathbb{N}$. A graph is $d$-degenerate when its vertices admit an ordering in which every vertex has at most $d$ neighbors earlier in the ordering. Burr–Erdős conjecture.…

Let $d$ be sufficiently large, and let $G$ be a $d$-degenerate triangle-free graph with fractional chromatic number $\chi_f(G)$. Martinsson–Steiner conjecture. The following two as…

Zhang–Zhang conjecture. If

Degeneracy conjecture for proper conflict-free list coloring. If $G$ is a $d$-degenerate graph for some positive integer $d$, then $G$ is proper conflict-free $({\rm degree}+d)$-ch…

Let $H^\prec$ be an edge-ordered $d$-degenerate graph on $n$ vertices, and let $R_\prec(H^\prec)$ be its edge-ordered Ramsey number. Fox–Li conjecture. One has … This would improve…

Let $G$ be a loopless graph, and let $d(v)$ denote the degree of each vertex $v\in V(G)$. Given a function $F:V(G)\to 2^{\mathbb N}$, an orientation is $F$-avoiding if its out-degr…

Let $H$ be a planar maximal 3-degenerate graph. A subdivision of $H$ is a graph obtained by replacing edges by internally vertex-disjoint paths. Diwan's conjecture. Every graph wit…

Bounded-degeneracy linearity conjecture. For every integer $d\geq 1$, there exists a constant $c$ depending on $d$ such that

For each positive integer $k$, let $\alpha_k$ be the minimum value such that there is a constant $c_k$ with … whenever $G$ is $k$-degenerate and has maximum degree at most $D$. Let…

Let $k\in\mathbb{N}$, and let $G$ be a $k$-degenerate graph with a path of order $n\geq 1$. An induced path is a path whose vertices induce exactly the edges of the path in $G$. Es…

Bonamy–Bousquet–Feghali–Johnson conjecture. If $G=(V,E)$ is $d$-degenerate and $k>d$ is an integer, then $\mathcal{K}_k(G)$ has diameter

Esperet's conjecture. There is a constant $d$ such that every $k$-degenerate graph that has a path of order $n$ also has an induced path of order at least

Planar positive-valued cover conjecture. Under these assumptions, $H$ has a strictly $f$-degenerate transversal.

Let $d$ be a nonnegative integer, let $\mathcal D_d$ be the class of $d$-degenerate graphs, and let $H$ be a $d$-degenerate graph. For a graph $H$, let $\operatorname{flap}_d(H)$ d…

Fix an integer $D$. Degenerate-graph Ringel-type conjecture. There exists $n_0\in\mathbb{N}$ such that, for every $n\ge n_0$, if $G$ is a $D$-degenerate graph on $n$ vertices with…

A graph $G$ is $d$-degenerate if it has an ordering of its vertices $v_1,v_2,\ldots$ such that … for every $i\geq 1$. The upper density of a set $V\subseteq\mathbb N$ is…

Degenerate-graph density conjecture. For every fixed $k$-degenerate graph $H$,

Let $\bar\alpha_d$ denote the minimum, over planar graphs, of the maximum order of a $d$-degenerate induced subgraph divided by the number of vertices. The octahedron and icosahedr…

Extremal graph existence conjecture. For every integer $d\geq 2$, there exists a $d$-degenerate graph $H$ such that

Converse to the $(1,1)$-degeneracy characterization. If $H$ is a $2$-degenerate graph that is not $(1,1)$-degenerate, then

Equitable Vertex Arboricity Conjecture. Every graph with maximum degree at most $\Delta$ is equitably tree-$k$-colorable for every integer $k\geq (\Delta+1)/2$; equivalently,

An edge-ordered graph is a graph whose edges are equipped with a linear ordering. A graph is $d$-degenerate if every induced subgraph has a vertex of degree at most $d$. For an edg…

An edge-ordered graph is a graph whose edges are equipped with a linear ordering. A graph is $d$-degenerate if every induced subgraph has a vertex of degree at most $d$. For an edg…