# Parity constrained strongly connected orientations

Find a good characterization for undirected graphs having a strongly connected (more generally k-edge-connected) orientation so that the in-degree of every node is odd.

## Remarks

The analogous problem with rooted k-edge-connectivity requirement was solved by Frank, Jordán and Szigeti [1]. However, the natural extension of their characterization to the strongly connected case is not sufficient, as shown by an example by T. Király and Szabó [2].

Frank and Z. Király [3] characterized graphs which admit a T-odd and k-edge-connected orientation for every possible choice of subsets $T \subseteq V$ with $\vert E\vert+\vert T\vert$ even (an orientation is T-odd if a node has odd in-degree if and only if it is in T). A similar characterization for rooted k-edge-connectivity follows easily from the results in [1].

## References

1. A. Frank, T. Jordán, Z. Szigeti, An orientation theorem with parity conditions, Discrete Applied Mathematics 115 (2001) 37--45. DOI link
2. T. Király, J. Szabó, A note on parity constrained orientations, DOI link, EGRES Technical Report no. 2003-11
3. A. Frank, Z. Király, Graph orientations with edge-connection and parity constraints, Combinatorica 22 (2002), 47--70. DOI link