Group-colouring, group-connectivity, claw-decompositions, and orientations in 5-edge-connected planar graphs
R. Bruce Richter, Carsten Thomassen, Daniel H. Younger · Journal of Combinatorics · 2016
Let G be a graph, let Γ be an Abelian group with identity 0Γ, and, for each vertex v of G, let p(v) be a prescription such that ∑v∈V(G)p(v)=0Γ. A (Γ,p)-flow consists of an orientation D of G and, for each edge e of G, a label f(e) in Γ∖{0Γ} such that, for each vertex v of G, ∑e points in to v f(e)−∑e points out from v f(e)=p(v) If such an orientation D and labelling f exists for all such p,then G is Γ -connected. Our main result is that if G is a 5-edge-connected planar graph and |Γ|≥3, then G is Γ-connected. This is equivalent to a dual colourability statement proved by Lai and Li (2007): planar graphs with girth at least 5 are “Γ-colourable”. Our proof is considerably shorter than theirs. Moreover, the Γ -colourability result of Lai and Li is already a consequence of Thomassen’s (2003) 3-list-colour proof for planar graphs of girth at least 5. Our theorem (as well as the girth 5 colourability result) easily implies that every 5-edge-connected planar graph for which |E(G)| is a multiple of 3 has a claw decomposition, resolving a question of Barát and Thomassen. It also easily implies the dual of Grötzsch’s Theorem, that every planar graph without 1- or 3-cut has a 3-flow; this is equivalent to Grötzsch’s Theorem.