# Karp hardness of directed monochromatic triangle problem

Monochromatic problem is a classic NP-complete problem.

Does the complexity stay NP-complete if we use directed graph?

DIRECTED MONOCHROMATIC TRIANGLE problem:

Input: A digraph $$G(V,A)$$

Output: YES if there exists a triangle-free bipartition of $$A$$, otherwise NO.

A triangle-free bipartition of $$A$$ is a partition $$A=A_1\dot{\cup}A_2$$ such that both $$G[V,A_1]$$ and $$G[V,A_2]$$ are triangle-free.

Note that a triangle in a digraph is the set of $$3$$ vertices $$\{u,v,w\}$$ such that $$(u,v),(v,w),(w,u)\in A$$. It means that we only allow triangle that has consecutive arcs. For example, $$(u,v),(u,w),(w,u)$$ does NOT form a triangle.

Let $$\prec$$ be any total ordering of the vertices. For each edge $$(u, v) \in A$$, put it in $$A_1$$ if $$u \prec v$$, and in $$A_2$$ otherwise. Both $$(V, A_1)$$ and $$(V, A_2)$$ must be acyclic.