267 problems

Nash-Williams' conjecture. If

Ringel's conjecture. Every tree with $n+1$ vertices packs $2n+1$ times into the complete graph $K_{2n+1}$.

Kelly's conjecture. Every regular tournament has a Hamilton decomposition.

A decomposition of a graph is a partition of its edge set into subgraphs of the indicated types. Erdős–Gallai conjecture. Every $n$-vertex graph has a decomposition into $O(n)$ cyc…

A linear forest is a graph whose connected components are paths. The linear arboricity $\operatorname{la}(G)$ of a graph $G$ is the smallest number of linear forests whose union co…

Jackson's conjecture. Every regular bipartite tournament has a Hamilton decomposition.

Let $G$ be a planar, $4$-edge-connected, $4$-regular simple graph whose size is divisible by $3$. A claw-decomposition is a partition of the edges of $G$ into subgraphs isomorphic…

Let $k\geq 3$, and color the edges of the complete graph $K_{2k}$ so that each color class forms a perfect matching. A spanning tree is rainbow colored if no two of its edges have…

Dallard et al.'s conjecture. Such graphs have bounded tree-independence number; equivalently, they admit tree decompositions whose bags induce subgraphs of bounded independence num…

Fractional triangle decomposition threshold conjecture. For every $\varepsilon>0$ and $p \geq (1+\varepsilon) \sqrt{\frac{3 \log n}{2n}}$, w.h.p. $G(n,p)$ admits a fractional trian…

Strong Nine Dragon Tree Conjecture. If

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…

Kühn–Osthus conjecture. Every regular tripartite tournament has a Hamilton decomposition.

Let $n\ge3$ be odd, and let $G$ be a complete geometric graph on $n$ vertices that can be decomposed into $\left\lceil\frac{n}{2}\right\rceil+1$ plane star-forests. Convex-hull-siz…

Bang-Jensen–Yeo conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph has a strong arc decomposition.

Alspach–Mason–Pullman conjecture. This lower bound is attained for every tournament $T$ of even order.

Let $G$ be a graph, and let $k,d$ be nonnegative integers. The Nine Dragon Tree Conjecture. If … then $G$ decomposes into $k+1$ forests, one of which is $d$-bounded. The conjecture…

Graham–Häggkvist conjecture. The edge set of $K_{n,n}$ can be decomposed into copies of every $n$-edge tree $T$.

Gronau–Mullin–Rosa conjecture. For every $n$-vertex tree $T$ other than the path on $4$ vertices, $K_n$ has an orthogonal double cover by copies of $T$.

Let $K_n$ be the complete graph on $n$ vertices, and let a proper edge-colouring be an edge-colouring in which adjacent edges receive different colours. A rainbow spanning tree is…

Pikhurko–Sousa conjecture. There is an integer $n_0=n_0(H)$ such that

Erdős' conjecture. For each integer $g\geq 3$ and all sufficiently large $n\equiv 1,3\pmod 6$, there exists a Steiner triple system on $n$ elements with girth at least $g$.

Let $K_n$ be a complete graph and let a $1$-factorization be an edge-colouring whose colour classes form a decomposition of $K_n$ into perfect matchings. A subgraph is rainbow if a…

Let $T_1,\dots,T_n$ be trees such that, for each $i\in[n]$, $T_i$ has $i$ vertices. Define … A decomposition of $G$ into $T_1,\dots,T_n$ is a collection of pairwise edge-disjoint c…

A locally irregular graph is a graph in which adjacent vertices have distinct degrees. Let $\mathfrak{T}$ be a family of specific graphs of maximum degree at most three. Baudon et…