6 problems

For $k\in\mathbb{N}$, let $Q_{2k+1}$ denote the $(2k+1)$-dimensional hypercube. A graph is path-pairable if every pairing of its vertices can be joined by pairwise edge-disjoint pa…

For a positive integer $t$, let $K_t\square K_t\square K_t$ be the Cartesian product of three complete graphs on $t$ vertices. A graph is path-pairable if every pairing of its vert…

Let $t$ be a positive integer and let $q$ be an upper bound on the maximum degree of the demand graph in the relevant complete-grid path-pairing problem. Faudree–Gyárfás–Lehel dema…

Let $G$ be a path-pairable graph on $n$ vertices, and let $\frac{\log n}{\log\log n}$ denote the lower-bound order of magnitude for its maximum degree. Faudree–Gyárfás–Lehel degree…

Cartesian-product conjecture. There exist non-path-pairable graphs $G$ and $H$ such that

Asymptotic sharpness conjecture. This lower bound is asymptotically sharp: there should exist path-pairable graphs whose maximum degree has the right order of magnitude, namely…