Optimal path-decomposition conjecture for Johnson graphs
Optimal path-decomposition conjecture for Johnson graphs
Let be the -token graph of the complete graph , and let and denote pathwidth and treewidth. Optimal path-decomposition conjecture. The path decomposition of constructed in the paper is optimal, and
The conjecture is based on computational verification for the case and is then formulated for general . The source does not report a proof or disproof.
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.