Faerbung durch gerichtete Graphen

Verfasser: Gutjahr, Wolfgang
Sachtitel: Faerbung durch gerichtete Graphen. [Mit Fig. u. Tab.]
Herausgeber: Graz 1991. 67 Bl. 4
Impressum: Graz, Techn. Univ., Inst. f. Grundlagen d. Informationsverarbeitung, Diplomarb. v. 1991.
Standort: Hauptbibliothek - Magazin
Signatur: II 74.537a

Abstract
Sind G=(V_G,E_G) und H=(V_H,E_H) gerichtete Graphen, dann heisst G H-faerbbar, wenn es einen Graphenhomomorphismus f:V_G->V_H gibt, d.h. eine Abbildung der Knoten von G in die von H derart, dass fuer jede Kante (u,v) in E_G die Kante (f(u),f(v)) in E_H ist. In dieser Arbeit wird fuer fixe Graphen H die Komplexitaet des Problems untersucht, ob ein beliebiger Graph G H-faerbbar ist. Fuer ungerichtete Graphen war bereits gezeigt, dass H-faerben polynomiell ist, falls H bipartit ist, NP-vollstaendig sonst. Im allgemeineren Fall der gerichteten Graphen konnte bisher keine Gesamtklassifizierung gefunden werden. Schon die Untersuchung der Graphen mit 4 Knoten, hier vollstaendig durchgefuehrt, war recht aufwendig. Der Schwerpunkt der Arbeit liegt auf der polynomiellen Seite. Zunaechst konnte ein polynomieller Algorithmus fuer die sogenannten X-Underbar-Graphen eine Klasse, die auch alle Semipfade (Wege) enthaelt gefunden und erweitert werden. Dann wurde nach Einfuehrung von Farbmengengraphen bewiesen, dass unbalanzierte Semikreise in P sind. Ein eigenes Kapitel ist Gegenbeispielen gewidmet, die mehrere sich aufdraengende Vermutungen ueber Polynomialitaet bzw. NP-vollstaendigkeit von Graphenfamilien widerlegen und damit eine Gesamtklassifizierung unwahrscheinlich erscheinen lassen.

Betreuer
Maurer H./Welzl E.

Institut für Informationsverarbeitung und Computergestützte neue Medien