Geodesic
Partitions of some planar graphs into two linear forests
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 95-102 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A linear forest is a forest in which every component is a path. It is known that the set of vertices V(G) of any outerplanar graph G can be partitioned into two disjoint subsets V₁,V₂ such that induced subgraphs 〈V₁〉 and 〈V₂〉 are linear forests (we say G has an (LF, LF)-partition). In this paper, we present an extension of the above result to the class of planar graphs with a given number of internal vertices (i.e., vertices that do not belong to the external face at a certain fixed embedding of the graph G in the plane). We prove that there exists an (LF, LF)-partition for any plane graph G when certain conditions on the degree of the internal vertices and their neighbourhoods are satisfied.
Keywords: linear forest, bipartition, planar graphs 
@article{DMGT_1997_17_1_a5,
     author = {Borowiecki, Piotr and Ha{\l}uszczak, Mariusz},
     title = {Partitions of some planar graphs into two linear forests},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {95--102},
     year = {1997},
     volume = {17},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a5/}
}
TY  - JOUR
AU  - Borowiecki, Piotr
AU  - Hałuszczak, Mariusz
TI  - Partitions of some planar graphs into two linear forests
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 95
EP  - 102
VL  - 17
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a5/
LA  - en
ID  - DMGT_1997_17_1_a5
ER  - 
%0 Journal Article
%A Borowiecki, Piotr
%A Hałuszczak, Mariusz
%T Partitions of some planar graphs into two linear forests
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 95-102
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a5/
%G en
%F DMGT_1997_17_1_a5
Borowiecki, Piotr; Hałuszczak, Mariusz. Partitions of some planar graphs into two linear forests. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 95-102. http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a5/

[1] M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68.

[2] P. Borowiecki, P-Bipartitions of Graphs, Vishwa International J. GraphTheory 2 (1993) 109-116.

[3] I. Broere, C.M. Mynhardt, Generalized colourings of outerplanar and planar graphs, in: Graph Theory with Applications to Algorithms and Computer Science (Wiley, New York, 1985) 151-161.

[4] W. Goddard, Acyclic colourings of planar graphs, Discrete Math. 91 (1991) 91-94, doi: 10.1016/0012-365X(91)90166-Y.

[5] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995).

[6] P. Mihók, On the vertex partition numbers, in: M. Fiedler, ed., Graphs and Other Combinatorial Topics, Proc. Third Czech. Symp. Graph Theory, Prague, 1982 (Teubner-Verlag, Leipzig, 1983) 183-188.

[7] K.S. Poh, On the Linear Vertex-Arboricity of a Planar Graph, J. Graph Theory 14 (1990) 73-75, doi: 10.1002/jgt.3190140108.

[8] J. Wang, On point-linear arboricity of planar graphs, Discrete Math. 72 (1988) 381-384, doi: 10.1016/0012-365X(88)90229-4.