Given a complete graph whose edges are colored by 3 colors, a compatible 3-coloring is a coloring of nodes such that no edge of the graph has the same color as its end-points.
The best algorithm I know is quasi-polynomial time. The problem is not known to be NP-complete. What is known about the status of this problem ?