Acyclic orientation with parity constraints
Problem 1. Find a good characterization for undirected graphs having an acyclic orientation so that the in-degree of every node is even.
Problem 2. Find a good characterization for undirected graphs [math]\displaystyle G=(V,E)[/math] and [math]\displaystyle T\subseteq V[/math], having an acyclic orientation so that the in-degree of a node is odd iff it is in [math]\displaystyle T.[/math]
Problem 3. Find a good characterization for undirected graphs [math]\displaystyle G=(V,E)[/math] which, for every possible [math]\displaystyle T\subsetneq V[/math] satisfying [math]\displaystyle |T|+|E|[/math] even, have an acyclic orientation so that the in-degree of a node is odd iff it is in [math]\displaystyle T.[/math]
Remarks
Problem 2 is a generalization of open problem Characterization of dual-critical graphs, while Problem 1 is another interesting special case of Problem 2. The corresponding problem, when we are looking for a strongly connected orientation instead of an acyclic orientation, is also open, while the strongly connected version of Problem 3 is solved by Frank and Z. Király [1].
See also
Characterization of dual-critical graphs, Parity constrained strongly connected_orientations and Acyclic orientation with connectivity presciptions.
