A dual version of the Brooks group coloring theorem

Abstract Let G be a 2-edge-connected undirected graph, A be an (additive) Abelian group, and A ∗ = A − { 0 } . A graph G is A - connected if G has an orientation D ( G ) such that for every mapping b : V ( G ) ↦ A satisfying ∑ v ∈ V ( G ) b ( v ) = 0 , there is a function f : E ( G ) ↦ A ∗ such that for each vertex v ∈ V ( G ) , the sum of f over the edges directed out from v minus the sum of f over the edges directed into v equals b ( v ) . For a 2-edge-connected graph G , define Λ g ( G ) = min { k : for any Abelian group A with | A | ≥ k , G is A -connected } . Let P denote a path in G , let β G ( P ) be the minimum length of a circuit containing P , and let β i ( G ) be the maximum of β G ( P ) over paths of length i in G . We show that Λ g ( G ) ≤ β i ( G ) + 1 for any integer i > 0 and for any 2-connected graph G . Partial solutions toward determining the graphs for which equality holds were obtained by Fan et al. in [G. Fan, H.-J. Lai, R. Xu, C.-Q. Zhang, C. Zhou, Nowhere-zero 3-flows in triangularly connected graphs, Journal of Combinatorial Theory, Series B 98 (6) (2008) 1325–1336], among others. In this paper, we completely determine all graphs G with Λ g ( G ) = β 2 ( G ) + 1 .