# 3Col reduction Variation, Special edges

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.

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)\}$$.