An algorithm for colouring perfect planar graphs (Q1825203)

A graph G is perfect if for every induced subgraph \(G'\) of G the chromatic number of \(G'\) equals the size of the largest clique of \(G'\). This paper uses the Lipton-Tarjan separator algorithm for planar graphs to construct an \(O(n^{3/2})\) algorithm to minimally color a perfect planar graph. A set of vertices C is called a separator if the n vertices of G can be partitioned into sets A, B, C such that no edge of G joins a vertex of A with a vertex of B and further neither A nor B contains more than 2n/3 vertices. The Lipton-Tarjan algorithm finds a separator of size at most \((8n)^{1/2}\) in a planar graph in linear time.