Acyclic orientation with parity constraints

Definitions and mathematical statement

Let $G=(V,E)$ be a finite loopless undirected graph; parallel edges, if present, are counted separately. An orientation chooses one direction for each edge. It is acyclic if it contains no directed cycle. For $T\subseteq V$, a $T$-parity orientation satisfies \[ d_D^-(v)\equiv\begin{cases}1&v\in T,\\0&v\notin T\end{cases} \pmod2, \] where $d_D^-(v)$ counts arcs entering $v$.

Give a structural, effectively usable characterization of the pairs $(G,T)$ admitting an acyclic $T$-parity orientation. The all-even case $T=\varnothing$ is a separately highlighted subproblem. An equivalent ordering formulation asks for a linear ordering of $V$ in which each vertex has an odd number of incident edges to earlier vertices exactly when it belongs to $T$.

The third source question asks which graphs have this property for every proper subset $T\subsetneq V$ satisfying \[ |T|\equiv|E|\pmod2. \] An orientation may be chosen separately for each such $T$. The parity condition is necessary because the sum of all indegrees is $|E|$; every connected component also has its own parity constraint. Excluding $T=V$ is natural because a nonempty finite acyclic digraph has a source of indegree zero. These necessary observations alone are not offered as a sufficient characterization. Exhaustive enumeration of vertex orders is finite, but does not provide the sought structural description or an efficient recognition method.

Short English statement

Characterize acyclic graph orientations with prescribed indegree parity, including graphs supporting every admissible proper parity set.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000003 (AMR-029-0003), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Acyclic orientation with parity constraints. Original source indexed by AMR-029-0003. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Acyclic orientation with parity constraints. Individual source statement and remarks. https://lemon.cs.elte.hu/egres/open/Acyclic_orientation_with_parity_constraints.