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: http://dx.doi.org/10.4310/JOC.2016.v7.n2.a1

Authors

R. Bruce Richter (Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada)

Carsten Thomassen (Department of Applied Mathematics and Computer Science, Technical University of Denmark, Lyngby, Denmark)

Daniel H. Younger (Department of Combinatorics and Optimization, University of Waterloo, Ontario, Canada)

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.

Full Text (PDF format)