DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  17(1) (1997)   95-102
DOI: 10.7151/dmgt.1042

PARTITIONS OF SOME PLANAR GRAPHS INTO TWO LINEAR FORESTS

Piotr Borowiecki
and
Mariusz Hałuszczak

Institute of Mathematics
Technical University of Zielona Góra
Podgórna 50, 65-246 Zielona Góra, Poland

 e-mail:    p.borowiecki@im.uz.zgora.pl

   m.haluszczak@im.uz.zgora.pl

Abstract

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 V1,V2 such that induced subgraphs ⟨V1 ⟩ and ⟨V2 ⟩ 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.

1991 Mathematics Subject Classification: 05C15, 05C70.

References

[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.