On Group Chromatic Number of Graphs

Let G be a graph and A an Abelian group. Denote by F(G, A) the set of all functions from E(G) to A. Denote by D an orientation of E(G). For f ∈ F(G,A), an (A,f)-coloring of G under the orientation D is a function c : V(G)↦A such that for every directed edge uv from u to v, c(u)−c(v) ≠ f(uv). G is A-colorable under the orientation D if for any function f ∈ F(G, A), G has an (A, f)-coloring. It is known that A-colorability is independent of the choice of the orientation. The group chromatic number of a graph G is defined to be the least positive integer m for which G is A-colorable for any Abelian group A of order ≥m, and is denoted by χ_g(G). In this note we will prove the following results. (1) Let H₁ and H₂ be two subgraphs of G such that V(H₁)∩V(H₂)=∅ and V(H₁)∪V(H₂)=V(G). Then χ_g(G)≤min{max{χ_g(H₁), max_v∈V(H2)deg(v,G)+1},max{χ_g(H₂), max_u∈V(H1) deg (u, G) + 1}}. We also show that this bound is best possible. (2) If G is a simple graph without a K_3,3-minor, then χ_g(G)≤5.