<p>The fastest known algorithm has running time $n^{O(\log n/ \log \log n)}$ [1].<br/>
Your question is reposed as an open problem in [2, page 4].</p>

<p>[1]: T. Feder, P. Hell, D. Kr&aacute;l, and J. Sgall. Two algorithms for general list matrix partitions. SODA 2005, pages 870–876.</p>

<p>[2]: E. D. Demaine, M. Hajiaghayi, D. Marx. Open Problems -- Parameterized complexity and approximation algorithms. Dagstuhl Seminar 09511 (2009). Available <a href="http://drops.dagstuhl.de/opus/volltexte/2010/2499/" rel="nofollow">here</a>.</p>

CC BY-SA 2.5
2010-08-26T19:30:16.797Z
2010-08-26T19:30:16.797Z
Serge Gaspers
<p>Apparently, this paper by Cygan, Pilipczuk, Pilipczuk and Wojtaszczyk (2010+) gives a faster (polynomial time) algorithm: <a href="http://arxiv.org/abs/1004.5010" rel="nofollow">http://arxiv.org/abs/1004.5010</a></p>

<p>It was accepted to SODA 2011.</p>

CC BY-SA 2.5
2010-09-25T14:59:37.313Z
2010-09-27T14:33:51.403Z
2010-09-27T14:33:51.403Z
RJK
<p>Given a complete graph whose edges are colored by 3 colors, <em>a compatible 3-coloring</em> is a coloring of nodes such that no edge of the graph has the same color as its end-points.</p>

<p>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 ? </p>

CC BY-SA 2.5
2010-08-26T19:30:10.423Z
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 ?
Suresh Venkat
CC BY-SA 2.5
2010-08-26T20:31:01.417Z
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.
Serge Gaspers
<cc.complexity-theory><ds.algorithms><reference-request><graph-theory>
What is the complexity of computing a compatible 3-coloring of a complete graph?
Mohammad Al-Turkistany
# What is the complexity of computing a compatible 3-coloring of a complete graph?

(Asked by: username_0 on 2010-08-26)

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 ?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, graph-theory

> **Comments:**
> **username_1**: 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 ?  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_3 on 2010-09-25. Score: 6 | Accepted answer

Apparently, this paper by Cygan, Pilipczuk, Pilipczuk and Wojtaszczyk (2010+) gives a faster (polynomial time) algorithm: <http://arxiv.org/abs/1004.5010>

It was accepted to SODA 2011.


---

### Answer by username_2 on 2010-08-26. Score: 5

The fastest known algorithm has running time $n^{O(\log n/ \log \log n)}$ [1].  
Your question is reposed as an open problem in [2, page 4].

[1]: T. Feder, P. Hell, D. Král, and J. Sgall. Two algorithms for general list matrix partitions. SODA 2005, pages 870–876.

[2]: E. D. Demaine, M. Hajiaghayi, D. Marx. Open Problems -- Parameterized complexity and approximation algorithms. Dagstuhl Seminar 09511 (2009). Available [here](http://drops.dagstuhl.de/opus/volltexte/2010/2499/).


---

