Über die chromatische Zahl der Graphen mit 1-Einbettung in eine Pseudoebene

Abstract

1965 führte Ringel den Begriff der 1-Einbettbarkeit eines Graphen in eine Fläche ein, wonach jede Kante im Innern von nicht mehr als einer einzigen anderen Kante gekreuzt werden kann. Dort zeigte Ringel auch auf, daß man einen beliebigen Graphen mit 1-Einbettung in eine Ebene mit 7 Farben färben kann, und äußerte die Vermutung, daß man auch mit 6 Farben auskommen kann. Am Beispiel eines Dreieckprismas, in dem alle 6 Diagonalen auf die Seitenkanten verlaufen, zeigte er, daß man mit weniger als 6 Farben nicht auskommt. 1984 gelang dem Verfasser des vorliegenden Artikels der Beweis der Ringelschen Vermutung. Nachstehend wird eine Verallgemeinerung dieses Ergebnisses am Fall einer 1-Einbettung von Graphen S(p) Sinne von "a" mitgeteilt.