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