𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Another Proof of the Map Color Theorem for Nonorientable Surfaces

✍ Scribed by Vladimir P. Korzhik

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
523 KB
Volume
86
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

The simplest known proof of the Map Color Theorem for nonorientable surfaces (obtained by Youngs, Ringel et al. and given in Ringel's book ''Map Color Theorem'') uses index one and three current graphs, and index two and three inductive constructions. We give another proof, still using current graphs, but simpler than Youngs' and Ringel's in several ways. Our proof uses only index one current graphs and no inductive constructions. For every h58; h=9; 14; we construct an index one current graph GðhÞ that yields a minimal nonorientable embedding cðhÞ of K h : The current graphs GðhÞ have the property that GðnÞ and Gðn þ 1Þ are not too different from each other and share common ladder-like fragments. As a result, the embeddings cðnÞ and cðn þ 1Þ have a large number of common faces: it is shown that, as n approaches infinity, for nc3; 9 mod 12 (resp. n 3; 9 mod 12Þ no less than 5/8 (resp. 5/16) of all faces of cðnÞ appear in cðn þ 1Þ:

📜 SIMILAR VOLUMES

A Simpler Proof of the Excluded Minor Th
A Simpler Proof of the Excluded Minor Theorem for Higher Surfaces
✍ Carsten Thomassen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We give a simple proof of the fact (which follows from the Robertson Seymour theory) that a graph which is minimal of genus g cannot contain a subdivision of a large grid. Combining this with the tree-width theorem and the quasi-wellordering of graphs of bounded tree-width in the Robertson Seymour t

The last excluded case of Dirac's map-co
The last excluded case of Dirac's map-color theorem for choosability
✍ Daniel Král'; Riste S̆krekovski 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB

## Abstract In 1890, Heawood established the upper bound $H ( \varepsilon )= \left \lfloor 7+\sqrt {24\varepsilon +1}/{2}\right \rfloor$ on the chromatic number of every graph embedded on a surface of Euler genus ε ≥ 1. Almost 80 years later, the bound was shown to be tight by Ringel and Youngs. Th