Kedlaya, Kiran S. Outerplanar partitions of planar graphs. (English) Zbl 0858.05040 J. Comb. Theory, Ser. B 67, No. 2, 238-248 (1996). 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) Cited in 10 Documents MSC: 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:edge-partition; embedding; Whitney’s theorem; outerplanar graph; conjecture of Chartrand, Geller and Hedetniemi; planar graph; outerplanar partitions; outerplanar subgraphs PDFBibTeX XMLCite \textit{K. S. Kedlaya}, J. Comb. Theory, Ser. B 67, No. 2, 238--248 (1996; Zbl 0858.05040) Full Text: DOI