27 problems

Let $\pi_1$ be a graphic degree sequence, and let $\mathbf{k}$ denote the degree sequence in which every term is $k$. Two graphic degree sequences pack when they have realizations…

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…

Given graphs $F$ and $G$, a subdivision packing of $F$ in $G$ is a collection of pairwise vertex-disjoint copies of subdivisions of $F$. For a real number $\eta > 0$ and a graph…

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

Yuster's triangle-packing 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…

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…

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:

Let $T_1,\dotsc,T_n$ be trees, and let $v(T_i)$ denote the number of vertices of $T_i$. A collection of graphs packs into a graph $G$ if there are edge-disjoint subgraphs of $G$ is…

Let $G$ be a graph on $n$ vertices with minimum degree $\delta(G)\ge n/2$. Kühn–Lapinskas–Osthus conjecture. The graph $G$ contains $\operatorname{reg}_{\operatorname{even}}(G)/2$…

Perfect-packing conjecture. There is an integer $n_0=n_0(\gamma,H)$ such that, whenever $n\geq n_0$, $|H|$ divides $n$, and

Degree-sequence conjecture. If

Frieze–Krivelevich conjecture. Asymptotically almost surely, $G$ contains

Average-degree tree-packing conjecture. If $G$ has average degree at least $k-1$, equivalently at least

Minimum-degree tree-packing conjecture. If $G$ satisfies