Edge-critical subgraphs of Schrijver graphs

Abstract

For $k\ge 1$ and $n\ge 2k$, the Kneser graph $KG(n,k)$ has all $k$-element subsets of an $n$-element set as vertices; two such subsets are adjacent if they are disjoint. It was first proved by Lovász that the chromatic number of $KG(n,k)$ is $n-2k+2$. Schrijver constructed a vertex-critical subgraph $SG(n,k)$ of $KG(n,k)$ with the same chromatic number. For the stronger notion of criticality defined in terms of removing edges, however, no analogous construction is known except in trivial cases. We provide such a construction for $k=2$ and arbitrary $n\ge 4$ by means of a nice explicit combinatorial definition.

Cited by in corpus (2)

• Edge-critical subgraphs of Schrijver graphs II: The general case
• Monochromatic spanning trees and matchings in ordered complete graphs