lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find an NP-complete problem and reduce it to my problem.
I tried it with general 3-colorability, but I was unable to create function F() that would reduce a general graph to a triangle-free graph without changing its colorability.
Is it a good direction? Does it make sense to reduce the 3-colorability problem?
If yes, I would appreciate any advice on how to finish the proof. If I am doing it wrong, I would appreciate any advice on the reduction.