We present a polynomial time algorithm for the 3-Compatible colouring problem, where we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. Consequently we complete the proof of a dichotomy for the k-Compatible Colouring problem. The tractability of the 3-Compatible colouring problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] - a quasipolynomial algorithm with a n~(O(log n/log log n)) time complexity. Furthermore our result implies a polynomial algorithm for the Stubborn problem which enables us to finish the classification of all List Matrix Partition variants for matrices of size at most four over subsets of {0,1} started by Cameron et al. [SODA'04].
展开▼
