# 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 $\displaystyle G=(V,E)$ and $\displaystyle T\subseteq V$, having an acyclic orientation so that the in-degree of a node is odd iff it is in $\displaystyle T.$

Problem 3. Find a good characterization for undirected graphs $\displaystyle G=(V,E)$ which, for every possible $\displaystyle T\subsetneq V$ satisfying $\displaystyle |T|+|E|$ even, have an acyclic orientation so that the in-degree of a node is odd iff it is in $\displaystyle T.$

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

## References

1. A. Frank, Z. Király, Graph orientations with edge-connection and parity constraints, Combinatorica 22 (2002), 47--70. DOI link