Grinberg-Introduction-Graph-Theory · Problem 6.3

Colorings

Mathematics — Graph Theory · kneser-graph-colorings

Problem

Fix two positive integers

n

and

k

with

n \geq 2k > 0

. Let

S = \{1, 2, \ldots, n\}

. Consider the

k

-Kneser graph

K_{S,k}

as defined in Subsection 2.6.3. Prove that

K_{S,k}

has a proper

(n - 2k + 2)

-coloring. [Hint: What can you say about the minima (i.e., smallest elements) of two disjoint subsets of

S

? (Being distinct is a good first step.)] [Remark: L\'{o}vasz has proved in 1978 (using topology!) that this result is optimal -- in the sense that

n - 2k + 2

is the smallest integer

q

such that

K_{S,k}

has a proper

q

-coloring.]