1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.