Group colorings of graphs

Daniel Kráľ1

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.


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