12 problems

Bollobás–Eldridge–Catlin packing conjecture. Every such graph $G$ contains every such graph $H$ whose maximum degree is at most $\Delta$. The conjecture asserts a sharp minimum-deg…

In a digraph $D=(V,A)$, a dicut is a set of arcs of the form $\delta^+(U)$ for a nonempty proper subset $U\subsetneqq V$ such that $\delta^-(U)=\emptyset$, and a dijoin is a set of…

Let $D$ and $D'$ be digraphs, and let $|A(D)|$ denote the size of $D$, meaning its number of arcs. For every integer $n$ and every $m$ satisfying … write $\mu(n,k)$ for the smalles…

Let $n\ge 3$ be an integer, and let $(d_1^1,\ldots,d_n^1)$ and $(d_1^2,\ldots,d_n^2)$ be graphic sequences with $d_n^1,d_n^2\ge 1$. Two graphic sequences pack when there are edge-d…

Signed planar signature-packing conjecture. Any signed planar graph in

Let $G$ be a graph on $N$ vertices. Suppose there is a parameter $W$ such that, for every induced subgraph $G'$ and every $n$, all but at most … edges of $G'$ are contained in some…

Let $m>w\ge 1$. The Kneser graph $\operatorname{KG}(m,w)$ has as vertices the $w$-element subsets of an $m$-element set, with two vertices adjacent when the corresponding subsets a…

Let $T_2,T_3,\ldots,T_n$ be trees such that each $T_i$ has order $i$. A graph is $k$-chromatic if its chromatic number is $k$, and $K_{n-1,\lceil\frac{n}{2}\rceil}$ denotes the com…

Let $C_n$ be a cycle of order $n=2k+x$, with $k\geq2$ and $1\leq x\leq2k-1$. The parameter $\lambda^k(C_n)$ is the largest number of labels in a labeling of the vertices that admit…

Floor half-Ore-degree packing conjecture. If

Let $G_1$ and $G_2$ be graphs on $n$ vertices, and let $E(G_i)$ and $\Delta(G_i)$ denote the edge set and maximum degree of $G_i$, respectively. Two graphs pack if there is a bijec…

Let $n$ be a positive integer. Consider any family of trees in which every individual tree has order at most $n+1$ and the total number of edges is at most $\binom{2n+1}{2}$. Stren…