Group chromatic number of planar graphs of girth at least 4

Abstract

Abstract Jeager et al. introduced a concept of group connectivity as a generalization of nowhere zero flows and its dual concept group coloring, and conjectured that every 5‐edge connected graph is Z 3 ‐connected. For planar graphs, this is equivalent to that every planar graph with girth at least 5 must have group chromatic number at most 3. In this article, we show that if G is a plane graph with girth at least 4 such that all 4 cycles are independent, every 4‐cycle is a facial cycle and the distance between every pair of a 4‐cycle and a 5‐cycle is at least 1, then the group chromatic number of G is at most 3. As a special case, we show that the conjecture above holds for planar graphs. We also prove that if G is a connected K 3,3 ‐minor free graph with girth at least 5, then the group chromatic number is at most 3. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 51–72, 2006