# 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.