An iV‐colour theorem for sequentially constructed planar graphs with myopic colouring
Sydney C. K. Chu · International Journal of Mathematical Education in Science and Technology · 1988
While the four‐colour conjecture is a difficult problem, any planar graph can be easily shown to be five‐colourable. This paper shows that a planar graph needs only a small number of different colours provided complete information of the graph prior to any actual colouring attempt is available. If (1) we draw a planar graph one node at a time with edges incident only to nodes already drawn, and (2) a node just included receives immediately a lower index colour different from all its neighbours in the absence of future information (myopic painting), then we can produce planar graphs requiring as many different colours as we please. Specifically, to force the use of Ncolours needs such a sequentially constructed planar graph with F(N)nodes, where F(N)is the iVth Fibonacci number with F(l) = l and F(2) = 2.