What is the complexity of computing a compatible 3-coloring of a complete graph?
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.