15. ÖMG-Kongress
Jahrestagung der Deutschen Mathematikervereinigung

16. bis 22. September 2001 in Wien

Sektion 3 - Diskrete Mathematik, Algorithmen
Dienstag, 18. September 2001, 15.30, Hörsaal 23

 

Das Kreis-und-Dreiecke-Theorem: Implikationen und Verallgemeinerungen

Herbert Fleischner, Österreichische Akademie der Wissenschaften

 

Das Kreis-und-Dreiecke-Theorem besagt, dass jeder in einen Hamiltonschen Kreis und Dreiecke zerlegbare 4-reguläre Graph 3-färbbar ist. Daraus ergeben sich ursprünglich nicht vorhergesehene Implikationen und Anwendungen in verschiedene Richtungen wie etwa Matching Theorie, die Theorie der ganzzahligen Flüsse, sowie die Kreis-Doppelüberdeckungs-Vermutung. Verallgemeinert man das Problem auf 4-reguläre Graphen, die in einen Hamiltonschen Kreis und beliebige konform eingeschriebene Kreise zerlegbar sind, so sind das Problem der Bestimmung der chromatischen Zahl und die Frage nach einer unabhängigen $(n/3)$-Knotenmenge NP-vollständige Probleme.

E-Mail:	fleischner@oeaw.ac.at
Homepage:	www.dismat.oeaw.ac.at/Fleischner.shtml

Zeitplan der Sektion   Tagesübersicht   Liste der Vortragenden