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

Let $G$ be a graph with maximum degree $\Delta$ and edge-chromatic number $\chi'(G)=\Delta+k$, and let $p,q$ be positive integers satisfying … with $p,q\leq\Delta$. A graph is clas…

Let a pure graph $G$ (or its parity class $[G]$) be primitive when, for every family $\mathcal{F}$ of pure classes, $[G]\in\overline{\mathcal{F}}$ implies $[G]\in\mathcal{F}$. A pu…

For $0\leq m\leq k$, define … Thus $\chi_0(k;K_n)=\omega(k;K_n)$ and $\chi_k(k;K_n)=\chi(k;K_n)$. Mixed decomposition conjecture. Let $m$ and $n\geq 1$ be non-negative integers. Th…

A $k$-decomposition of the complete graph $K_n$ is a decomposition into $k$ spanning subgraphs $G_1,\ldots,G_k$, and for a graph parameter $p$ let … Here $\chi$ denotes chromatic n…

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…

Odd-cycle decomposition threshold conjecture.

Approximate Oberwolfach Nash-Williams' conjecture. For every $\varepsilon>0$, for all sufficiently large $n$, if

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

Fractional Nash-Williams' conjecture. If

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

Critical-excess conjecture. If

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.

Let $D$ be a digraph. A branching is a digraph whose components are arborescences, and write $\gamma(D)$ for the directed fractional packing parameter and $\Delta^-$ and $\Delta^+$…

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…

Let $K_n$ be the complete graph on $n$ vertices, let $C_n$ be a Hamilton cycle on these vertices, and let $C_n^2$ denote its square, obtained by joining pairs at distance at most t…

A $(j,i)$-configuration in a family of sets is a collection of $i$ members spanning at most $j$ ground-set elements; the girth of a triangle packing is the smallest $i\geq 2$ for w…

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…

Pach–Saghafian–Schnider conjecture. For any $n\ge k\ge 2$,

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 $G$ be a $6$-regular graph. A 2-factor is a spanning $2$-regular subgraph, and a component of a $2$-factor is one of its connected components. The 6-regular three-2-factor conj…

Partite folklore conjecture. For each integer $q\geq 4$, the following holds for sufficiently large $n$: if $G$ is a balanced partite-$K_q$-divisible $q$-partite graph on $qn$ vert…

Partite Nash-Williams conjecture. For sufficiently large $n$, if $G$ is a balanced partite-$K_3$-divisible $3$-partite graph on $3n$ vertices with