Speaker: Matěj Stehlík

Title: Edge-critical subgraphs of Kneser and Schrijver graphs.

Abstract: In 1978, Lovasz proved a famous conjecture about the chromatic number of Kneser graphs using a theorem from topology. Shortly thereafter, Schrijver sharpened the result by showing that certain induced subgraphs of Kneser graphs, the so-called Schrijver graphs, have the same chromatic number. Moreover, he showed that Schrijver graphs are vertex-critical, in the sense that the chromatic number decreases if any vertex is deleted. However, Schrijver graphs are in general not edge-critical: certain edges can be deleted without any effect on the chromatic number. In this talk, I will define a family of subgraphs of Schrijver graphs, show that they have the same chromatic number, and prove that they are edge-critical, thereby sharpening the classical results of Lovasz and Schrijver.

Joint work with Tomáš Kaiser.