On $4$-chromatic Schrijver graphs: their structure, non-$3$-colorability, and critical edges

Gábor Simonyi, Gábor Tardos

We give an elementary proof for the non-$3$-colorability of $4$-chromatic Schrijver graphs thus providing such a proof also for $4$-chromatic Kneser graphs. To this end we use a co…