Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-6399
Autor(en): | Borodin, O. V. |
Titel: | Über die chromatische Zahl der Graphen mit 1-Einbettung in eine Pseudoebene |
Erscheinungsdatum: | 1998 |
Dokumentart: | Verschiedenartige Texte |
Erschienen in: | Originaltext erschienen in: Metody diskretnogo analiza v teorii grafov i logiceskich funkcij 43 (1986), S. 3-11 |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-78955 http://elib.uni-stuttgart.de/handle/11682/6416 http://dx.doi.org/10.18419/opus-6399 |
Zusammenfassung: | 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. |
Enthalten in den Sammlungen: | 13 Zentrale Universitätseinrichtungen |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
Ue_512_Borodin.pdf | 764,74 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.