Contents Online
Journal of Combinatorics
Volume 7 (2016)
Number 2–3
Guest editors: Rong Luo and Cun-Quan Zhang
Group-colouring, group-connectivity, claw-decompositions, and orientations in 5-edge-connected planar graphs
Pages: 219 – 232
DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a1
Authors
Abstract
Let $G$ be a graph, let $\Gamma$ be an Abelian group with identity $0_\Gamma$, and, for each vertex $v$ of $G$, let $p(v)$ be a prescription such that $\sum_{v\in V(G)}p(v)=0_\Gamma$. A $(\Gamma,p)$-flow consists of an orientation $D$ of $G$ and, for each edge $e$ of $G$, a label $f(e)$ in $\Gamma\setminus\{0_\Gamma\}$ such that, for each vertex $v$ of $G$,\[\sum_{e\textrm{ points in to }v}f(e)-\sum_{e\textrm{ points out from }v}f(e)=p(v).\]If such an orientation $D$ and labelling $f$ exists for all such $p$,then $G$ is $\Gamma$-connected.
Our main result is that if $G$ is a 5-edge-connected planar graph and $|\Gamma|\ge3$, then $G$ is $\Gamma$-connected. This is equivalent to a dual colourability statement proved by Lai and Li (2007): planar graphs with girth at least 5 are “$\Gamma$-colourable”. Our proof is considerably shorter than theirs. Moreover, the $\Gamma$-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.
Published 23 February 2016