On 4-chromatic Schrijver graphs: their structure, non-3-colorability, and critical edges A Story with Drums($)

摘要

We investigate 4-chromatic Schrijver graphs from various points of view and color-critical edges in Schrijver graphs in general. In particular, we present the following results. 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. We show that only certain types of edges of Schrijver graphs can be color-critical and prove that many of those are indeed color-critical, though in general not all of them are. In the 4-chromatic case these results give a complete characterization of the color-critical edges. We show that a spanning subgraph of 4-chromatic Schrijver graphs quadrangulates the Klein bottle, while another spanning subgraph quadrangulates the projective plane. The latter is a special case of a result by Kaiser and Stehlik. We show that (apart from two cases of small parameters) the subgraphs we present that quadrangulate the Klein bottle are edge-color-critical. The analogous result for the subgraphs quadrangulating the projective plane is an immediate consequence of earlier results by Gimbel and Thomassen and was already noted by Kaiser and Stehlik. Our proof of non-3-colorability of 4-chromatic Schrijver graphs is based on a complete description of their structure that we present as well. This was already also given (in somewhat different terms) by Braun and even earlier in an unpublished manuscript by Li.