On the Treewidth of Token and Johnson Graphs

Let G be a graph on n vertices and 1 k n a fixed integer. The k-token graph of G is the graph, Fₖ (G), whose vertex set is equal to all the k-subsets of V (G) ; where two of them are adjacent whenever their symmetric difference is an edge of G. In this paper we study the treewidth of Fₖ (G), when G is a star, path or a complete graph. We show that in the first two cases, the treewidth is of order (n^k-1), and of order (nᵏ) in the third case. We conjecture that our upper bound for the treewidth of Fₖ (Kₙ) is tight. This is particularly relevant since Fₖ (Kₙ) is isomorphic to the well known Johnson graph J (n, k).