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 -Knotenmenge NP-vollständige Probleme.
E-Mail: | fleischner@oeaw.ac.at |
Homepage: | www.dismat.oeaw.ac.at/Fleischner.shtml |