On 4-Chromatic Schrijver Graphs: Their Structure, Non-3-Colorability, and Critical Edges : A Story with Drums

Simonyi, Gábor and Tardos, Gábor (2020) On 4-Chromatic Schrijver Graphs: Their Structure, Non-3-Colorability, and Critical Edges : A Story with Drums. ACTA MATHEMATICA HUNGARICA, 161. pp. 583-617. ISSN 0236-5294 (print); 1588-2632 (online)

Preview

Text 1912.pdf Available under License Creative Commons Attribution. Download (449kB) | Preview

Abstract

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-chromaticSchrijver graphs thus providing such a proof also for 4-chromatic Knesergraphs.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 of4-chromatic Schrijver graphs quadrangulates the Klein bottle, while anotherspanning subgraph quadrangulates the projective plane. The latter is aspecial case of a result by Kaiser and Stehlík.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 Stehlík. 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.

Actions (login required)

Edit Item