Color-critical edges in Schrijver graphs

The vertices of the Kneser graph $KG(n,k)$ are the $k$-subsets of an $n$-element base set and two vertices are connected if they are disjoint subsets. (Here $n$ and $k$ are integers and we assume $n>2k-1$.) Proving Kneser's conjecture Lovász established in 1978 that the chromatic number of $KG(n,k)$ is $n-2k+2$. The proof jumpstarted combinatorial applications of topology. In the same year Schrijver defined the graph $SG(n,k)$ as the subgraph of $KG(n,k)$ induced by independent sets if the base set is considered as the vertex set of a cycle. He proved that $SG(n,k)$ has the same chromatic number as $KG(n,k)$ but it is vertex-critical: removing any one vertex from $SG(n,k)$ decreases its chromatic number. But $SG(n,k)$ is not edge-critical: the removal of some edges does not decrease its chromatic number. This started a quest in two directions: to find out which edges of $SG(n,k)$ are color-critical and to find edge-critical subgraphs of $SG(n,k)$ with the same chromatic number. Both problems are solved in the case of 4-chromatic Schrijver graphs that are closely related to quadrangulations of surfaces, for the latter problem Kaiser and Stehlik gave nice examples. The talk also contains partial results and conjectures for the general case.

Joint work with Gábor Simonyi (Rényi Institute / Budapest Institute of Technology and Economics).