Graph Orientations and Signings That Are Saturated with Alternating Cycles

Abstract

The edges of a graph can be either directed or signed (\(2\)-colored) so as to make some of the even-length cycles of the underlying graph into alternating cycles. If a graph has a signing in which every even-length cycle is alternating, then it also has an orientation in which every even-length cycle is alternating, but not conversely. The existence of such an orientation or signing is closely related to the existence of an orientation in which every even-length cycle is a directed cycle.