On Partitioning Planar Graphs
Canadian mathematical bulletin, Tome 11 (1968) no. 2, pp. 203-211
Voir la notice de l'article provenant de la source Cambridge
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.
Hedetniemi, Stephen. On Partitioning Planar Graphs. Canadian mathematical bulletin, Tome 11 (1968) no. 2, pp. 203-211. doi: 10.4153/CMB-1968-023-5
@article{10_4153_CMB_1968_023_5,
author = {Hedetniemi, Stephen},
title = {On {Partitioning} {Planar} {Graphs}},
journal = {Canadian mathematical bulletin},
pages = {203--211},
year = {1968},
volume = {11},
number = {2},
doi = {10.4153/CMB-1968-023-5},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1968-023-5/}
}
Cité par Sources :