Johnson graph pathwidth conjecture

About 2 years old · traced to

For integers nn and kk with 1≤k≤n−11\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.

References

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.