Premium
Group chromatic number of planar graphs of girth at least 4
Author(s) -
Lai HongJian,
Li Xiangwen
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20147
Subject(s) - combinatorics , mathematics , planar graph , girth (graph theory) , discrete mathematics , odd graph , conjecture , triangle free graph , chromatic scale , graph , 1 planar graph , chordal graph
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