Graph orientations with edge-connection and parity constraints (Q1603262)

For a graph \(G=(V,E)\), we say \(T\subseteq V\) is \(G\)-even if \(|T|+|E|\) is even. An orientation of \(G\) is \(T\)-odd if the in-degree of a node \(v\) is odd precisely when \(v\in T\). The main result of this paper is an NP and co-NP characterization of graphs admitting the property `\(G\) has an \(l\)-edge-connected \(T\)-odd orientation for every \(G\)-even subset \(T\) of nodes'. As a corollary it is also shown that every \(4\)-edge-connected graph \(G=(V,E)\) with a \(G\)-even subset \(T\) has a strongly connected \(T\)-odd orientation. Several related results combining parity and connectivity requirements are imposed.