Johnson graph pathwidth conjecture

For integers nn and kk with 1kn11\le k\le n-1, let Fk(Kn)F_k(K_n) be the kk-token graph of the complete graph KnK_n, 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

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

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

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.