Kneser graph

Kneser Graphs as State Graphs and Fractional Chromatic Number... 

Considering the elementary definition of the Kneser graphs, it turned out to be surprisingly difHcult to determine their chromatic numbers. 

Simplicial and Cubical Complexes Associated to Kneser Graphs... 

To finish the proof of the Kneser conjecture (Theorem 17.21), we still need to see that the neighborhood complex of Kneser graphs is sufficiently connected. In fact, it turns out that the homotopy type of these complexes can be determined precisely. 

Theorem 17.21 now foUows. Though this is a short and clarifying proof of Proposition 17.28, we shall investigate the complexes associated to Kneser graphs at some further length to imcover some interesting cubical constructions and to illustrate some other techniques that we developed in Part II. 

Shortly after it was published, Lov z s resolution of the Kneser conjecture was complemented by finding a maximal subgraph having the same chromatic number as the original Kneser graph. To formulate this result, we recall that a graph G is called vertex-critical if for any vertex v G V G), we have x G) = x G-v) + l. 

Sr78] A. Schrijver, Vertex-critical subgraphs of Kneser graphs, Nieuw Arch. Wiskd., III. Ser., (1978), pp. 454-461. 

The Kneser conjecture states that in fact equality holds. This was proved in 1978 by L. Lovasz, who used geometric obstructions of Borsuk-Ulam type to show the nonexistence of certain graph colorings. 

---