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.