Geodesic
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 University Press

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/}
}
TY  - JOUR
AU  - Hedetniemi, Stephen
TI  - On Partitioning Planar Graphs
JO  - Canadian mathematical bulletin
PY  - 1968
SP  - 203
EP  - 211
VL  - 11
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1968-023-5/
DO  - 10.4153/CMB-1968-023-5
ID  - 10_4153_CMB_1968_023_5
ER  - 
%0 Journal Article
%A Hedetniemi, Stephen
%T On Partitioning Planar Graphs
%J Canadian mathematical bulletin
%D 1968
%P 203-211
%V 11
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1968-023-5/
%R 10.4153/CMB-1968-023-5
%F 10_4153_CMB_1968_023_5

[1] 1. Chartrand, G. and Harary, F., Planar permutation graphs. Ann. Inst. Henri Poincare, Section B, 3(1967)433-438. Google Scholar

[2] 2. Hadwiger, H., Uber eine klassification der Streckenkomplexe. Viertelischr. Naturforsch. Ges. Zurich, 88 (1943) 133-142. Google Scholar

[3] 3. Harary, F., A seminar on graph theory. Holt, Rinehart, and Winston, , New York, (1967) 1-41. Google Scholar

[4] 4. Heawood, P., Map colour theorem. Quart. J. Pure Appl. Math. 24 (1890) 332. Google Scholar

[5] 5. Kempe, A.B., On the geographical problem of the four colours. Amer. J. Math. 2 (1879) 193-200. Google Scholar

[6] 6. Nash-Williams, C. St.J.A., Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36 (1961) 445-450. Google Scholar

[7] 7. Tang, D.T., A class of planar graphs containing Hamilton circuits. Fourth Allerton Conference on Circuit and System Theory (1966). Google Scholar

Cité par Sources :