Satz von Ringel-Youngs

Der Satz von Ringel-Youngs, auch Heawood-Vermutung genannt, gibt in der Graphentheorie eine Formel für die minimale Anzahl der Farben, die für die Färbung einer beliebigen Fläche nötig ist abhängig vom topologischen Geschlecht der Fläche (wobei hier ein Geschlecht ${\displaystyle g>0}$ betrachtet wird).

Percy Heawood hatte die Formel 1890 angegeben, bewiesen, dass diese Formel für Geschlecht ${\displaystyle g>0}$ eine obere Schranke darstellt und die Vermutung formuliert, dass sie auch eine untere Schranke ist. Das heißt, er bewies, dass jede Landkarte auf den entsprechenden Flächen mit der durch die Formel angegebenen Anzahl von Farben färbbar ist, und vermutete, dass man im Allgemeinen nicht mit weniger Farben auskommt. 1968 wurde das von Gerhard Ringel und J. W. T. Youngs bewiesen, mit Ausnahme der Fälle der Kleinschen Flasche und der Kugel. Der Fall der Kugel (Geschlecht g=0) entspricht dem schwierigen Fall des Vier-Farben-Satzes (wobei hier das Problem darin liegt die obere Schranke zu beweisen, für die untere Schranke kann man eine einfache Landkarte angeben, die nur mit vier Farben färbbar ist) und wurde erst 1977 bewiesen, die Formel ist aber auch hier gültig. Die Kleinsche Flasche blieb eine Ausnahme für die Gültigkeit der Formel.