A Note on Group Colorings and Group Structure
Hong‐Jian Lai, Lucian Mazza · SIAM Journal on Discrete Mathematics · 2021
Abelian group colorings were first introduced by Jaeger et al. in [ J. Combin. Theory Ser. B, 56 (1992), pp. 165--182] as the dual concept of group connectivity of graphs. For given groups $\Gamma_1$ and $\Gamma_2$ with $|\Gamma_1| = |\Gamma_2|$, the dual version of a problem raised by Jaeger et al. suggests to investigate whether every $\Gamma_1$-colorable graph $G$ is also $\Gamma_2$-colorable. Recently, Hǔsek, Mohelníková, and Šámal [ J. Graph Theory, 93 (2019), pp. 317--327] used computer testing to find the first examples of $\mathbb{Z}_4$-connected but not $\mathbb{Z}_2^2$-connected graphs as well as $\mathbb{Z}_2^2$-connected but not $\mathbb{Z}_4$-connected graphs. As their examples are nonplanar, the group coloring problem remains unanswered. Group coloring was extended to non-abelian groups in Li and Lai [ Discrete Math., 313 (2013), pp. 101--104]. We introduce a group coloring local structure (defined as a snarl in the paper) and use it to construct infinitely many ordered triples $(G, \Gamma_1, \Gamma_2)$ in which $G$ is a graph and $\Gamma_1$ and $\Gamma_2$ are groups with $|\Gamma_1| = |\Gamma_2|$, such that $G$ is $\Gamma_1$-colorable but not $\Gamma_2$-colorable.