37 problems

Verstraëte's conjecture. For every graph $H$ and every $\eta>0$, there exists a threshold number $r_0$ such that every $n$-vertex, $r$-regular graph $G$ with $r\ge r_0$ contains a…

Bollobás–Eldridge conjecture. If

A tree of order $i$ is a tree with $i$ vertices, and a collection of graphs can be packed into a graph when they can be embedded edge-disjointly. Gyárfás–Lehel Tree Packing Conject…

Gruslys's conjecture. If $|V(H)|$ divides $|V(G)|$, then there exists a positive integer $n$ such that $G^n$ admits a perfect induced $H$-packing.

Kawarabayashi's conjecture. If

Kühn–Osthus conjecture. The graph $G$ has an $H$-packing leaving at most a constant number of vertices of $G$ uncovered.

Let $H=(V,E,A)$ be a mixed graph, let $\mathcal{D}(V)$ denote the relevant family of subpartitions, and let $d_A^-(X)$ count arcs entering $X$. Let $k\geq0$ and $d\geq1$ be integer…

Infinite-group characterization conjecture. The family $\mathcal{F}$ satisfies the half-integral Erdős–Pósa property, and it satisfies the Erdős–Pósa property if and only if…

Prescribed-parity matching conjecture. If $p\geq n^{-1/2}$, then asymptotically almost surely $G(n,p)$ contains a perfect matching on

Odd-vertex matching conjecture. If

Let $k\ge 2$ and let $G$ be a $k$-partite graph with parts $V_1,\ldots,V_k$ of the same size $n$. Define the partite minimum degree of $G$ to be the largest integer $d$ such that e…

McDonald–Puleo–Tennenhouse conjecture.

Let $f(k)$ be the maximum number of extremal edges of a convex-packable plane path with $k$ edges. The source establishes the upper bound $f(k)\leq 2\sqrt{k}$ for every positive in…

Let $\mathcal{P}(G)$ denote the set of plane drawings of a graph $G$, and let $\Theta_2$, $\Theta_3$, and $\Theta_4$ be the three plane triangulated cycles shown in the source. A s…

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…

Fix an integer $r$. Bounded-regular graph packing conjecture. There exists $n_0\in\mathbb{N}$ such that, for every $n\ge n_0$, any family of $n$-vertex graphs $(G_s)_{s\in[N]}$ in…

Let a tree family be a family $(T_s)_{s\in[N]}$ of trees. Bounded-degree tree-family packing conjecture. There exist $\delta>0$ and $n_0\in\mathbb{N}$ such that, for every…

Let $n\in\mathbb{N}$, and let $(T_s)_{s\in[n]}$ be a family of trees such that $v(T_s)=s$ for every $s\in[n]$. Tree packing conjecture. The family $(T_s)_{s\in[n]}$ packs into the…

Let $\kappa$ be an infinite cardinal, let $K_\kappa$ denote the complete graph on $\kappa$ vertices, and let $\mathcal{T}$ be a family of trees. Require that $\mathcal{T}$ contain…

Let $f(n)$ be the largest number $m$ such that every $2$-colouring of the edges of $K_n$ contains a packing of edge-disjoint monochromatic triangles whose total number of edges is…

Let $H_1,\dots,H_t$ be a collection of $n$-vertex graphs with bounded degree, let $K_n$ be the complete graph on $n$ vertices, and let $e(H_i)$ denote the number of edges of $H_i$.…

Finite-obstruction meta-conjecture. If there is no simple obstruction to packing $\mathcal{G}$ into $H$, then a packing exists; equivalently, there is a finite list of obstructions…

Odd-prime-power torus packing conjecture. There exists $n_0$ such that, for all $n \ge n_0$, $C_k^n$ admits a perfect induced $H$-packing.

Gruslys, Leader and Tan's conjecture. For $kge 1$, there exists a positive integer $n$ such that the edges of $Q_n$ can be covered by edge-disjoint copies of $H$; the copies of $H$…

Alon–Spencer's conjecture. The trivial upper bound gives the true order of magnitude of the expected packing number: