On Partitioning Planar Graphs

Abstract

In 1879 Kempe [5] presented what has become the most famous of all incorrect proofs of the Four Colour Conjecture, but even though his proof was erroneous his method has become quite useful. In 1890 Heawood [4] was able to modify Kempe's method to establish the Five Colour Theorem for planar graphs. In this article we show that other modifications of Kempe's method can be made which enable one to establish more results about planar graphs. By this process we obtain upper bounds for several parameters which involve partitioning the point set of a graph. In particular, we show that the point set of any planar graph can be partitioned into four or less subsets such that the subgraph induced by each subset is either disconnected or trivial (consists of a single point). We also show that the point set of any planar graph can be partitioned into three or less subsets such that the subgraph induced by each subset contains no cycles.