40 problems

Cereceda's conjecture. For any $d$-degenerate graph $G$ and $d+2$, the diameter of $$ is $O(n^2)$.

Let $G$ be a $d$-degenerate graph with maximum degree at most $\Delta$. A proper coloring is equitable when its color classes differ in size by at most one. Kostochka–Nakprasit's c…

Wu, Zhang and Li's conjecture. Every graph with maximum degree $\Delta$ has an equitable tree-$k$-coloring for every

Let $G$ be a $k$-degenerate graph, meaning that every subgraph of $G$ contains a vertex of degree at most $k$, and let $c7_s^{\prime}(G)$ denote its strong chromatic index. Chang–N…

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…

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…

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 graph, and let $L$ be a $k$-assignment, meaning that each vertex $v$ has a list $L(v)$ of $k$ available colors. Let $\mathcal{C}_L(G)$ be the graph whose vertices are…

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…

Let $G$ be a graph, let $G^2$ denote its square, let $\Delta(G)$ be its maximum degree, let $\chi(G^2)$ be the chromatic number of $G^2$, and let $\operatorname{mad}(G)$ be its max…

Let $D$ be a positive integer, let $\mathcal{H}(n,D)$ be the class of all $n$-vertex $D$-degenerate graphs, and let an $\mathcal{H}(n,D)$-universal graph be a graph containing ever…

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…

Harris's conjecture. There is an absolute constant implicit in the $O$-notation such that

Bartier et al.'s conjecture. If $k\geq d+3$, then

Let $r$ be a fixed positive integer. A graph is $r$-degenerate if its vertices can be linearly ordered so that each vertex has back degree at most $r$. Let $H$ be an $r$-degenerate…

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…