11 problems

A digraph is Eulerian when it is strongly connected and every vertex has equal in-degree and out-degree. Its average out-degree is the average of the out-degrees of its vertices; d…

Treewidth-bounded immersion conjecture. The class of Eulerian digraphs of treewidth at most $k$ is well-quasi-ordered by immersion.

Weak immersion conjecture. The class of Eulerian digraphs is well-quasi-ordered by weak immersion.

Johnson's conjecture. For every $d\geq 1$, the class of Eulerian digraphs of maximum degree $2d$ is well-quasi-ordered by strong immersion.

Let $D$ be a directed Eulerian graph, meaning a digraph in which every vertex satisfies $d^+(v)=d^-(v)$. A cycle decomposition partitions the directed edges into directed cycles. D…

Let $G$ be an Eulerian directed graph on $n$ vertices, meaning that its indegree equals its outdegree at every vertex. Bollobás–Scott partition conjecture. The edge set of $G$ can…

Let $G$ be a connected Eulerian directed graph with average degree at least $d$, and let a directed path be a sequence of consistently oriented edges. Huang–Ma–Shapira–Sudakov–Yust…

Let $G$ be a finite loopless directed graph, allowing both orientations of an edge, and write $d^+(v)$ and $d^-(v)$ for the outdegree and indegree of a vertex $v$. The graph is Eul…

Fixed-arc deletion algorithm conjecture. For each fixed positive integer $k$, there exists a polynomial-time algorithm which, given a semicomplete digraph $D=(V,A)$ and…

Spanning eulerian subdigraph avoidance conjecture. Every $(k+1)$-arc-strong semicomplete digraph $D$ has a spanning eulerian subdigraph that avoids any prescribed set of $k$ arcs.

Let $D$ be an Eulerian digraph with no loops or digons. For each vertex $v\in V(D)$, let $N^{+}(v)$ and $N^{+2}(v)$ denote its first and second out-neighborhoods, respectively. Ave…