On the diameter of Schrijver graphs

Authors

Abstract: For

k g e q 1

and

n g e q 2 k

, the well known Kneser graph

o p e r a t o r n a m e K G (n, k)

has all

k

-element subsets of an

n

-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph

o p e r a t o r n a m e S G (n, k)

of

o p e r a t o r n a m e K G (n, k)

with the same chromatic number. In this paper, we compute the diameter of the graph

o p e r a t o r n a m e S G (2 k + r, k)

with

r g e q 1

. We obtain an exact value of the diameter of

o p e r a t o r n a m e S G (2 k + r, k)

when

r i n 1, 2

or when

r g e q k - 3

. For the remained cases, when

3 l e q r l e q k - 4

, we obtain that the diameter of

o p e r a t o r n a m e S G (2 k + r, k)

belongs to the integer interval

[4.. k - r - 1]

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: On the diameter of Schrijver graphs