# 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 [math] T \subseteq V[/math] with [math]\vert E\vert+\vert T\vert[/math] 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.0}^{1.1}A. Frank, T. Jordán, Z. Szigeti,*An orientation theorem with parity conditions*, Discrete Applied Mathematics 115 (2001) 37--45. DOI link - ↑ T. Király, J. Szabó,
*A note on parity constrained orientations*, DOI link, EGRES Technical Report no. 2003-11 - ↑ A. Frank, Z. Király,
*Graph orientations with edge-connection and parity constraints*, Combinatorica 22 (2002), 47--70. DOI link