×

Outerplanar partitions of planar graphs. (English) Zbl 0858.05040

Author’s abstract: An outerplanar graph is one that can be embedded in the plane so that all of the vertices lie on one of the faces. We investigate a conjecture of Chartrand, Geller, and Hedetniemi, that every planar graph can be edge-partitioned into two outerplanar subgraphs. We refute the stronger statement that every planarly embedded graph can be edge-partitioned into two outerplanar subgraphs, one of which is outerplanarly embedded. We give a method that yields outerplanar partitions of certain graphs not covered by previous results. We formulate a conjecture about 4-connected maximal planar graphs that implies the original conjecture. Finally, we verify a weaker form of the conjecture in which outerplanar subgraphs are replaced by subgraphs with no homeomorphs of \(K_4\).
Reviewer: K.Engel (Rostock)

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI