Alspach–Mason–Pullman conjecture on path decompositions of even tournaments
Alspach–Mason–Pullman conjecture on path decompositions of even tournaments
Let be a directed graph with vertex set and edge set . A path decomposition of is a collection of directed paths whose edge sets partition . Let be the minimum number of paths in a path decomposition of . For each vertex , define its excess by , its positive excess by , and its negative excess by . Define
A tournament is an orientation of a complete graph, and it is consistent when . Alspach–Mason–Pullman conjecture. Every tournament with an even number of vertices satisfies
The excess gives a general lower bound for the number of paths in a path decomposition. The conjecture asserts that this lower bound is always attained for even tournaments; the supplied source gives no resolution status.
Sources & referencesView supporting material
Primary source
Allan Lo, Viresh Patel, Jozef Skokan and John Talbot, “Decomposing tournaments into paths”, arXiv:1902.10775 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.