7 problems

Let $G$ be a connected graph on $n$ vertices, and let $p(G)$ denote the minimum number of paths in a path decomposition of $G$. Gallai's conjecture. … This conjecture is a central…

Pullman's conjecture. For odd $d$, every $d$-regular graph is strongly consistent. This generalizes the even-order tournament conjecture from complete graphs to all odd-regular gra…

For a graph $G$, let $\mathsf{path}\textnormal{-}\chi(G)$ denote its path-chromatic number. Path-chromatic two-colourability conjecture. It is NP-complete to decide if…

Let $Q_n$ be the $n$-dimensional hypercube, with edge set of size $n2^{n-1}$. A path decomposition of $Q_n$ is a decomposition of its edge set into paths of a common length. Erde's…

Kouider–Lonc's conjecture. If $G$ is $2\ell$-regular, then $G$ admits a balanced $P_\ell$-decomposition.

Let $G\sim G_{n,p}$, where $p=o(1)$ and $pn/\log n\to\infty$, and let $odd(G)$ denote the number of odd-degree vertices of $G$. Sparse random-graph path decomposition conjecture. A…

Let $n$ be an even positive integer, and let $k$ be a positive integer. The $n$-dimensional hypercube $\mathcal{Q}_n$ has vertex set $\{0,1\}^n$ and edges joining vertices at…