Group Connectivity and Group Coloring: Small Groups versus Large Groups

Abstract

A well-known result of Tutte says that if $\Gamma$ is an Abelian group and $G$ is a graph having a nowhere-zero $\Gamma$-flow, then $G$ has a nowhere-zero $\Gamma'$-flow for each Abelian group $\Gamma'$ whose order is at least the order of $\Gamma$. Jaeger, Linial, Payan, and Tarsi observed that this does not extend to their more general concept of group connectivity. Motivated by this we define $g(k)$ as the least number such that, if $G$ is $\Gamma$-connected for some Abelian group $\Gamma$ of order $k$, then $G$ is also $\Gamma'$-connected for every Abelian group $\Gamma'$ of order $|\Gamma'| \geqslant g(k)$. We prove that $g(k)$ exists and satisfies for infinitely many $k$,

\begin{align*}
(2-o(1)) k < g(k) \leqslant 8k^3+1.
\end{align*}

The upper bound holds for all $k$. Analogously, we define $h(k)$ as the least number such that, if $G$ is $\Gamma$-colorable for some Abelian group $\Gamma$ of order $k$, then $G$ is also $\Gamma'$-colorable for every Abelian group $\Gamma'$ of order $|\Gamma'| \geq h(k)$. Then $h(k)$ exists and satisfies for infinitely many $k$,

\begin{align*}
(2-o(1)) k < h(k) < (2+o(1))k \ln(k).
\end{align*}

The upper bound (for all $k$) follows from a result of Král', Pangrác, and Voss. The lower bound follows by duality from our lower bound on $g(k)$ as that bound is demonstrated by planar graphs.