157 problems

For positive integers $r\le s\le t$, the complete tripartite graph $K_{r,s,t}$ admits a decomposition into $5$-cycles if and only if $r\equiv s\equiv t\pmod{2}$,…

Daykin–Häggkvist conjecture. Given a partial Latin square $L$ of order $n$ in which each row, column, and symbol is used at most $n/4$ times, it is possible to complete $L$ into a…

Nash-Williams' conjecture. If $G$ is $K_3$-divisible and

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

Barát–Thomassen conjecture. For every tree $T$, there exists a positive integer $k_T$ such that every $k_T$-edge-connected simple graph whose size is divisible by $|E(T)|$ admits a…

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…

Let $n\geq 2$ be an even integer. A perfect $1$-factorisation of a graph is a partition of its edge set into perfect matchings such that the union of any two distinct perfect match…

Strong Nine Dragon Tree Conjecture. If

A regular bipartite tournament is an orientation of the complete balanced bipartite graph $K_{2n,2n}$ in which every vertex has indegree and outdegree $n$. A Hamilton decomposition…

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 $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's conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph $D=(V,A)$ has an arc-partition

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$.

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

Erdős meets Nash-Williams' conjecture. For every integer $g$, every sufficiently large $K_3$-divisible graph $G$ on $n$ vertices satisfying

Hypergraph Nash–Williams–Tutte conjecture. For positive integers $t$ and $k$, every $k$-weakly-partition-connected hypergraph $H$ on $t$ vertices has a $k$-distinguishable tree ass…

Linear Arboricity Conjecture.

Alspach et al.'s wreath-product conjecture. If $G$ and $H$ are hamiltonian decomposable directed graphs, then $G\wr H$ is also hamiltonian decomposable.

Böttcher–Hladký–Piguet–Taraz conjecture. Each family of trees of individual orders at most $n+1$ and total number of edges at most $\binom{2n+1}{2}$ packs into $K_{2n+1}$.

Let $G$ be a connected cubic graph. Hoffmann-Ostenhof's 3-Decomposition Conjecture. $G$ can be decomposed into a spanning tree, a collection of cycles, and a possibly empty matchin…

Planar Linear Arboricity Conjecture. For every planar graph $G$ of maximum degree $\Delta\ge 5$,

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

For a finite graph $G$, let $G^n$ be the graph with vertex set $V(G)^n$, in which two vertices are adjacent exactly when they differ in one coordinate and the entries in that coord…