4 problems

Linial's conjecture. For every digraph $D$ and every positive integer $k$,

Let $D$ be a digraph. A $k$-path subdigraph of $D$ is a collection of $k$ vertex-disjoint paths, and let $\lambda_k(D)$ denote the maximum order of a $k$-path subdigraph; in partic…

The relaxed partition number conjecture. For any $d$-regular graph $G$,

Let $G$ be a graph of order $n$, let $k\geq 3$ be an integer, and let $n_{1},\dots,n_{k}$ be positive integers satisfying … Write $\sigma_2(G)$ for the minimum degree sum of two no…