✦ LIBER ✦

The combinatorial map color theorem

✍ Scribed by Gerhard Ringel

Publisher: John Wiley and Sons
Year: 1977
Tongue: English
Weight: 522 KB
Volume: 1
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190010210

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper is written in the spirit of the author's book: Map Color Theorem (1974). We try to develop the Map Color Theorem in a combinatorial way, circumventing the unwieldy embedding theory. Similar (but not identical) generalizations have recently and independently been developed by Alpert (in press) and by Stahl (in press). The first nine theorems are one‐dimensional versions of known facts from the theory of two‐dimensional compact manifolds. Theorems 10 to 13 are to my knowledge completely new results.

📜 SIMILAR VOLUMES

Dirac's map-color theorem for choosabili

Dirac's map-color theorem for choosability

✍ B�hme, T.; Mohar, B.; Stiebitz, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 290 KB

It is proved that the choice number of every graph G embedded on a surface of Euler genus ε ≥ 1 and ε = 3 is at most the Heawood number H(ε) = (7 + √ 24ε + 1)/2 and that the equality holds if and only if G contains the complete graph K H(ε) as a subgraph.

Another Proof of the Map Color Theorem f

Another Proof of the Map Color Theorem for Nonorientable Surfaces

✍ Vladimir P. Korzhik 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 523 KB

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 graph

Combinatorial theorems on contractive ma

Combinatorial theorems on contractive mappings in power sets

✍ Egbert Harzheim 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 713 KB

We prove that to every positive integer n there exists a positive integer h such that the following holds: If S is a set of h elements and f a mapping of the pow+:r set 13 of S into b such that f(T) E T for all TE '@, then there exists a strictly increasing sequence TI c ---c T,, oi' subsets of S su

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

Note on the Colored Tverberg Theorem

✍ Jiřı&#x0301; Matoušek 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 305 KB

Theorem 1. For any integers r, d>1 there exists an integer T=T(d, r), such that given sets A 1 , ..., A d+1 /R d in general position, consisting of T points each, one can find disjoint (d+1)-point sets S 1 , ..., S r such that each S i contains exactly one point of each A j , j=1, 2, ..., d+1, and t

The four color theorem has been proved

📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 26 KB

On the 21st of June 1976, which was the 48th birthday of Wolfgang Haken, he and Kenneth Appel (with the aid of John Koch) completed their proof of the Four Color Theorem. In recognition of their momentous achievement, the Journal ofGruph Theory presents two articles (by Haken and by Frank Bernhart)