ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 17(1) (1997)
Institute of Mathematics
Technical University of Zielona Góra
Podgórna 50, 65-246 Zielona Góra, Poland
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.