Group colorings of graphs

Daniel Kráľ¹

MFF UK Praha and TU Berlin

We present several results on group coloring introduced by Jaeger et al. Group coloring is the dual concept of group connectivity, non-homogenous variant of nowhere-zero flows. We show that the group chromatic number of a graph with minimum degree d is greater than $d/(2 \log d)$ and answer several open questions on the group chromatic number of planar graphs. We also establish that the decision problem whether a graph $G$ is $A$-colorable is $\Pi_2$-complete for every fixed Abelian group $A$ of order three or more.

Footnotes

...ľ¹

joint work with P. Nejedlý, O. Pangrác and H.-J. Voss