# What is the complexity of computing a compatible 3-coloring of a complete graph?

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 ?

• Hi turkistany it would be very helpful if you were to provide more context for your questions, and this one in general. Specifically, what's a 'compatible' 3-coloring, and what's the history of the problem that you're already aware of ? Aug 26 '10 at 19:30
• The phrase "no edge of the graph has the same color as its end-points" might be somewhat ambiguous. What is meant is that for each edge, at least one of its endpoints has a different color than the edge. Aug 26 '10 at 20:31

The fastest known algorithm has running time $n^{O(\log n/ \log \log n)}$ [1].