Planar 3-colorability is polynomial complete
Larry Stockmeyer · ACM SIGACT News · 1973
The general problem of recognizing the set of pairs (G,k), where k is a positive integer and G is a graph which is k-colorable, is polynomial complete as defined by Karp [I].It is shown here that this problem is still complete even for pairs (G,k) where k = 3 and G is a planar graph.We assume that the reader is familiar with the definitions and notation of [1].The problems to be considered are the following. 3-COLORABILITY INPUT: Gra~.h G with nodes N and arcs A.PROPERTY: There is a function f: N-~ [1,2,3] such that if u, v are adjacent then f(u) # f(v).