Johnson graph pathwidth conjecture
Johnson graph pathwidth conjecture
For integers and with , let be the -token graph of the complete graph , also known as the Johnson graph. The tree decomposition of this graph constructed in the paper is a candidate decomposition. Johnson graph pathwidth conjecture. The decomposition is optimal, and
Moreover, the treewidth equals the upper bound established in the paper. The source gives no resolution of this conjecture; it is motivated by the authors' upper bound and computational evidence.
Sources & referencesView supporting material
Primary source
Ruy Fabila-Monroy, Sergio Gerardo Gómez-Galicia, César Hernández-Cruz and Ana Laura Trujillo-Negrete, “On the Treewidth of Token and Johnson Graphs”, arXiv:2402.17962 (2025).
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.