I have a question concerning NP reduction.

My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding out if the TRI-Graph is 3 coloring is NP-Complete.

I'm not asking for the answer. But I've been racking my brain on how to approach the reduction.

I'm curious to know if you guys have suggestions on which problem I should use to reduce it to my trigraph.

I've tried SAT3, CLIQUE, but those tri-edges make it very hard, maybe I'm going about it the wrong way.

Anyhow, any help would be appreciated. Thanks in advance.


1 Answer 1


You can reduce from $3$-coloring.

Given an instance (graph) $G=(V,E)$ of $3$-coloring, create a tri-graph $G'=(V', E')$ by transforming each edge $e=(u,v) \in E$ to a tri-edge $(u,v,z_e)$ in $G'$ (where $z_e$ is a new vertex).

A 3-coloring $c : V' \to \{1,2,3\}$ of $G'$ induces a $3$-coloring of $G$: simply color $v \in V$ with color $c(v)$. A 3-coloring $c : V \to \{1,2,3\}$ of $G$ can also be transformed into a $3$-coloring of $G'$ by coloring each vertex $z_e$, where $e=(u,v) \in E$, with the unique color in $\{1,2,3\} \setminus \{c(u), c(v)\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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