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.
The analogous problem with rooted k-edge-connectivity requirement was solved by Frank, Jordán and Szigeti . 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ó .
Frank and Z. Király  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 .
- 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