Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt

It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which pl…