Flüsse und Matchings in Graphen

Die Theorie der Graphenfärbung nimmt eine zentrale Stellung in der diskreten Mathematik und insbesondere der Graphentheorie ein. Die Forschung zur 4-Farben-Vermutung (seit 1976 als 4-Farben-Theorem etabliert) hat viele Bereiche der Graphentheorie geprägt. Tait (1880) zeigte, dass das 4-Farben-Theorem äquivalent zu der Behauptung ist, dass jeder planare brückenlose kubische Graph 3-Kanten-färbbar ist. Außerdem ist er äquivalent zu der Aussage, dass jeder planare brückenlose kubische Graph einen geraden 2-Faktor hat und dass jeder brückenlose planare Graph einen nirgendwo-nullen 4-Fluss hat. In diesem Projekt untersuchen wir diese Beziehungen in einem breiteren Kontext.

Förderer: Sino-German (CSC-DAAD) Postdoc Scholarship Program