Modulo orientations and matchings in graphs

The modulo orientation problem seeks a so-called mod (2t + 1)-orientation of an undirected graph, in which the indegree is equal to outdegree under modulo 2t + 1 at each vertex. Jaeger's circular flow conjecture states that every graph G with edge connectivity kappa' (G)& nbsp;>= 4t has a mod (2t +1)-orientation. Lovasz et al. (2013) verified it for kappa'(G) >=& nbsp;6t, and later Han et al. (2018) disproved Jaeger's conjecture with infinitely many counterexamples for t & GE; 3. In this paper, we show there are essentially finitely many exceptions for graphs with a bounded matching number. More generally, for any positive integers t and s, there exists a finite family G(t, s) of graphs not admitting any mod (2t + 1)-orientations, such that any graph G with kappa' (G) >= 2t + 2 and matching number alpha'(G) <=& nbsp;s has a mod (2t + 1)- orientation if and only if G cannot be contracted to an element of G(t, s). This immediately implies a Chvatal-Erdos type theorem and we additionally characterize all infinitely many graphs with kappa' >=& nbsp;alpha'& nbsp;but without a nowhere-zero 3-flow. Our results also indicate that the problem of seeking mod orientations for planar graphs with bounded matching number belongs to P, while for general planar graphs it is a known NP-complete problem. (C)& nbsp;2022 Elsevier B.V. All rights reserved.