Treewidth order conjecture for token graphs of trees

Let GG) be a tree on nn vertices, and let Fk(G)F_k(G) denote its kk-token graph, whose vertices are the kk-subsets of V(G)V(G). For a fixed integer kk satisfying 1kn11\le k\le n-1, the treewidth order conjecture for token graphs of trees.

tw(Fk(G))Θ(nk1).\operatorname{tw}(F_k(G)) \in \Theta(n^{k-1}).

This extends the established order of growth for token graphs of stars and paths to all trees. The conjecture is presented as open in the source.

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.