The [de Bruijn graph](https://en.wikipedia.org/wiki/De_Bruijn_graph) $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put an edge from the vertex $w_0 \dots w_{n-1}$ to the vertex $w_1
\dots w_n$. For the purposes of our problem, the edges are also $2$-colored,
where the color of the edge determined by $w \in 2^{n+1}$ is $w_0$.

Given a finite directed graph $G$ with a $2$-coloring on the edges, we ask
whether or not $G$ is the homomorphic image of $B_n$ for some $n$.

Is this problem decidable? That is, is there an algorithm which, given such a
$G$, answers "yes" if and only if there exist $n$ and a homomorphism $B_n \to
G$?

Here, a homomorphism is required to preserve the $2$-coloring on edges.
Formally, a homomorphism from $B_n$ to $G$ is a function $f \colon 2^n \to
V(G)$ such that for every edge $(u,v)$ of color $b$, $(f(u), f(v))$ is an edge
in $G$ of color $b$.

(We came upon this problem via an open problem in logic, see also our [recent
abstract](https://inria.hal.science/hal-04128087/file/UNIF_2023_paper_5.pdf).)