7 problems

Gallai's conjecture. The edge set of any $n$-vertex connected graph can be partitioned into at most

Magnant–Martin conjecture. Every $n$-vertex $d$-regular undirected graph has a path partition with at most $n/(d+1)$ paths; this bound would be tight for the disjoint union of…

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

For an $r$-coloured complete graph, let $\operatorname{pp}(r,1)$ be the minimum number of pairwise vertex-disjoint monochromatic paths whose vertices cover the graph. Path-partitio…

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…