Gallai’s Path Decomposition for Planar Graphs

Das Kapitel vertieft sich in Gallais Path Decomposition for Planar Graphs und konzentriert sich auf die langjährige Vermutung, dass jeder endliche, ungerichtete zusammenhängende Graph eine Zersetzung des k-Pfades zulässt. Obwohl die Vermutung für bestimmte Graphenklassen wie Graphen 2. oder 4. Grades, seriell-parallele Graphen und dreieckfreie planare Graphen bestätigt wurde, blieb sie ungelöst. Die Autoren gehen der Frage nach, ob jeder zusammenhängende Graph, der keine seltsame Semi-Clique ist, eine k-Pfad-Zersetzung zulässt, und beantworten dies positiv für planare Graphen. Das Hauptergebnis, Theorem 11, besagt, dass jeder zusammenhängende planare Graph, mit Ausnahme des Dreiecks und einer bestimmten Konfiguration, in Bahnen zerlegt werden kann. Der Beweis umfasst einen Standardansatz für die Färbung von Problemen, wobei ein Minimum an Gegenbeispielen und reduzierbaren Konfigurationen verwendet wird. Die Autoren entwickeln Reduktionsregeln für Eckpunkte geringen Grades und verwenden Eulers Formel, um den Beweis zu erbringen. Das Kapitel stellt auch Konfigurationen für spezielle Eckpunkte vor und stellt für jeden Fall eine Reihe von Reduktionsregeln vor, die eine gründliche und detaillierte Erforschung des Themas gewährleisten.