Treewidth of the generalized Kneser graphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

independence number treewidth of a graph

Structural characterization of families of graphs (05C75) Extremal set theory (05D05)

Abstract: Let

n

,

k

and

t

be integers with

1 l e q t < k l e q n

. The emph{generalized Kneser graph}

K (n, k, t)

is a graph whose vertices are the

k

-subsets of a fixed

n

-set, where two

k

-subsets

A

and

B

are adjacent if

| A c a p B | < t

. The graph

K (n, k, 1)

is the well-known emph{Kneser graph}. In 2014, Harvey and Wood determined the exact treewidth of the Kneser graphs for large

n

with respect to

k

. In this paper, we give the exact treewidth of the generalized Kneser graphs for

t g e q 2

and large

n

with respect to

k

and

t

. In the special case when

t = k - 1

, the graph

K (n, k, k - 1)

usually denoted by

o v e r l i n e J (n, k)

which is the complement of the Johnson graph

J (n, k)

. We give a more precise result for the exact value of the treewidth of

o v e r l i n e J (n, k)

for any

n

and

k

.

Review text

Summary: Let \(n\), \(k\) and \(t\) be integers with \(1\leqslant t< k \leqslant n\). The generalized Kneser graph \(K(n,k,t)\) is a graph whose vertices are the \(k\)-subsets of a fixed \(n\)-set, where two \(k\)-subsets \(A\) and \(B\) are adjacent if \(|A\cap B|<t\). The graph \(K(n, k, 1)\) is the well-known Kneser graph. \textit{D. J. Harvey} and \textit{D. R. Wood} [Electron. J. Comb. 21, No. 1, Research Paper P1.48, 11 p. (2014; Zbl 1300.05084)] determined the exact treewidth of the Kneser graphs for large \(n\) with respect to \(k\). In this paper, we give the exact treewidth of the generalized Kneser graphs for \(t\geqslant 2\) and large \(n\) with respect to \(k\) and \(t\). In the special case when \(t=k-1\), the graph \(K(n, k, k-1)\) is usually denoted by \(\overline{J(n,k)}\) which is the complement of the Johnson graph \(J(n, k)\). We give a more precise result for the exact value of the treewidth of \(\overline{J(n, k)}\) for any \(n\) and \(k\).

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Treewidth of the generalized Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2121803)