The Graph Coloring Problem

The problem: given a planar graph G and the number k, color G (means find a map V -> C, where V is a set of vertices of G, C is a set of k colors), such that no two adjacent vertices have the same color.
It is well-known that 3-coloring for planar graph is NP-complete.
Lipton and Miller (Information Processing Letter, 1978, v. 7, 4, "A batching method for coloring planar graphs") proved that 5-graph coloring is in O(n log n). They improved the result of D. Johnson, O(n^2) algorithm for 5-coloring (D. Johnson, Worst case behaviour of graph algorithm, 1974). After their result was impoved by Chiba, Nishizeki, Saito (A linear-time algorithm for five-coloring a planar graph, LNCS 108, 1981). Joseph Naor discovered that five coloring is in NC , or it can solved in polylogarithmic time on the machine with polynomial number of processors (to be more exact in O(log^5) time on O(n^3) processors)

The result is presented at J. Naor, A Fast Parallel Coloring Of Planar Graphs With Five Colors, Information Processing Letters 25(1987), 51-53

Herein the outline of the algorithm

Subroutine MAXINDSET: computing the maximal independent set of a planar graph: known to be in NC (log^2 time on n^3: Luby, A simple parallel coloring for the maximal independent set, SICOMP 15(4), 1986)

Algorithm is based on the recursion
COLORING
1 delete a set of independent vertices whose size is at least a fixed fraction A of the graph
2 apply COLORING to the remaining graph
3 extend the obtained coloring to the deleted vertices

since A is fixed, then the number of runs is logarithmic.
MAXINDSET is in NC, as well the set of deleted vertices is in NC
Extending the coloring is in NC

The Result is based on two simple lemmas
Lemma: More then 1/6 n vertices have degree less then 7
Proof: Suppose that the number of vertices with degree less then 7 is more then 1/6 n.
In that case the sum of degrees is more then 6n.
but it is known that the sum of the degrees in the planar graph is at most 6n-12

Lemma: Let U be a set of vertices whose degree is less then 7. The size of every maximal independent set in U[G] (induced subgraph defined by G) is at least 1/7|U|
Proof: obv.

So, the five coloring algorithm
COLORING

1 find a maximal independent set I in the induced subgraph defined by the vertices of degree less then 7
2 delete I from the graph G' = G \ I, apply COL = COLORING(G')
3 extend 5 coloring from G' to G
for each v in I
a the number of neighbours of v is less then 5, then color v; continue
b Let a and b be a pair of colors which as chosen by at least 1/10 of


TO BE COMLETED