Optimal path-decomposition conjecture for Johnson graphs

Let Fk(Kn)F_k(K_n) be the kk-token graph of the complete graph KnK_n, and let pw\operatorname{pw} and tw\operatorname{tw} denote pathwidth and treewidth. Optimal path-decomposition conjecture. The path decomposition of Fk(Kn)F_k(K_n) constructed in the paper is optimal, and

pw(Fk(Kn))=tw(Fk(Kn)).\operatorname{pw}(F_k(K_n))=\operatorname{tw}(F_k(K_n)).

The conjecture is based on computational verification for the case k=3k=3 and is then formulated for general kk. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.