80 problems

A linear forest is a collection of vertex-disjoint paths. For a graph $G$, its linear arboricity, denoted by $\operatorname{la}(G)$, is the minimum number of linear forests needed…

Let $\mathscr C$ be a class of tree-ordered weakly sparse graphs (TOWS graphs). A dense analogue of a weakly sparse class property is obtained by requiring every weakly sparse tran…

Let $\mathscr C$ be a hereditary weakly sparse class of graphs. An internal tree-ordering expansion of a graph is an expansion by the forest-ordering defined by a spanning forest;…

Let $c>0$ be a constant, let $H$ be a fixed graph, and let a graph be $(c,t)$-sparse if every pair of subsets $A,B$ of its vertex set with $|A|,|B|\geq t$ has at most $(1-c)|A||B|$…

Jackson–Jordán's conjecture. Every 5-regular, 3-sparse graph is $\mathcal{R}_3$-independent. This is the remaining case of the Jackson–Jordán characterization for graphs with bound…

Let $\mathcal{C}$ be a nowhere dense class of graphs, let $d$ be a positive integer, and let $\varepsilon$ be a positive real. For a graph $G$, write $G^d$ for its $d$th power, and…

Induced-path conjecture. There is a positive constant $c(k)$ such that the graph contains an induced path on

Let $\mathbb{G}(n,c/n)$ be the Erdős–Rényi random graph sequence and let $\mathbb{G}(n,\Delta)$ be the random regular graph sequence. Right-convergence is convergence of the normal…

Let $H$ be a fixed graph without isolated vertices. For $0<\beta<1$, let $\mathcal M_H(\beta)$ be the supremum of $t(H,W)$ over graphons $W$ with $t(K_2,W)\le\beta$. For…

Dvořák–Norin–Postle conjecture. Every $d$-degenerate graph is $\varepsilon$-flexibly $(d+1)$-choosable for some $\varepsilon>0$.

Let $H$ be a fixed graph. For each vertex $x\in V(H)$, let $V_x$ be a pairwise disjoint set of $n$ vertices, and let $\mathcal G(H,n,m)$ be the family of graphs with vertex set…

Induced grid-minor conjecture for sparse graph classes. Sparse graph classes should admit induced grid-minor theorems.

Kuperwasser–Samotij–Wigderson's conjecture. Every $(m,0)$-sparse graph can be partitioned into a $(1,-1)$-sparse graph and an $(m,1-2m)$-sparse graph.

Chen et al.'s conjecture. If $\theta(G)\ge 5$, then

Let $\mathscr C$ be a class of TOWS graphs, and let $\mathsf{Sp}(\mathscr C)$ be the class obtained by the paper's sparsifying transduction. Let $\Pi_S$ be a downset of weakly spar…

General $k$-degenerate-cut conjecture. Every graph of sufficiently large order $n$ with fewer than

Kaneko's conjecture. Every graph of order $n$ with fewer than $3n-6$ edges has a forest cut.

Li and Rousseau's conjecture.

Sparse restricted forest-coloring conjecture. Every $(\frac{9}{5},\frac{2}{5})$-sparse simple graph has an $(\mathcal{F}^{\Delta}_{1},\mathcal{F})$-coloring.

Polynomial-expansion lower-bound conjecture. For every real $b>0$, there exists a graph class with expansion $O(r^b)$ such that for infinitely many $p\in\mathbb N$ the class contai…

Let $\Pi$ be a graph-class property. A hereditary weakly sparse class is a hereditary graph class excluding some biclique $K_{t,t}$ as a subgraph. Meta-conjecture-ws$(\Pi)$. Every…

A hereditary weakly sparse class is a graph class closed under induced subgraphs and excluding some biclique $K_{t,t}$ as a subgraph. Hajebi's conjecture. Every hereditary weakly s…

Chen–Raspaud conjecture. For each integer $k\ge 2$, any graph $G$ satisfying

Let $G$ be a graph with $m$ edges and no isolated vertices, and let $r(G)$ denote its Ramsey number. Erdős's conjecture. There exists a constant $c>0$ such that, for every such gra…

Let $G$ be a finite, simple, undirected graph of order $n$, and call a vertex set a forest cut if it is a vertex cut whose induced subgraph is a forest. Forest-cut conjecture. If…