Journal article

Publication year: 2023

Pages: 477-486

Journal: Australasian journal of combinatorics

Volume number: 86

ISSN: 2202-3518

Publisher: Centre for Discrete Mathematics and Computing

Abstract: 

The generalized Kneser graph K(n, k, t) for integers k > t > 0 and n > 2k - t is the graph whose vertices are the k-subsets of {1,..., n} with two vertices adjacent if and only if they share fewer than t elements. We determine the treewidth of the generalized Kneser graphs K(n, k, t) when t >= 2 and n is sufficiently large compared to k. The imposed bound on n is a significant improvement of a previously known bound. One consequence of our result is the following. For each integer c >= 1 there exists a constant K(c) >= 2c such that k >= K(c) implies for t = k - c that

tw(K(n, k, t)) = (n k) - (n - t k - t) - 1

if and only if n >= (t + 1)(k + 1 - t).

Harvard Citation style: Metsch, K. (2023) On the treewidth of generalized Kneser graphs, Australasian journal of combinatorics, 86, pp. 477-486

APA Citation style: Metsch, K. (2023). On the treewidth of generalized Kneser graphs. Australasian journal of combinatorics. 86, 477-486.