Partitions of some planar graphs into two linear forests
Piotr Borowiecki; Mariusz Hałuszczak
Discussiones Mathematicae Graph Theory (1997)
- Volume: 17, Issue: 1, page 95-102
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topPiotr Borowiecki, and Mariusz Hałuszczak. "Partitions of some planar graphs into two linear forests." Discussiones Mathematicae Graph Theory 17.1 (1997): 95-102. <http://eudml.org/doc/270623>.
@article{PiotrBorowiecki1997,
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 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.},
author = {Piotr Borowiecki, Mariusz Hałuszczak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {linear forest; bipartition; planar graphs; outerplanar graph; internal vertices; embedding; plane graph},
language = {eng},
number = {1},
pages = {95-102},
title = {Partitions of some planar graphs into two linear forests},
url = {http://eudml.org/doc/270623},
volume = {17},
year = {1997},
}
TY - JOUR
AU - Piotr Borowiecki
AU - Mariusz Hałuszczak
TI - Partitions of some planar graphs into two linear forests
JO - Discussiones Mathematicae Graph Theory
PY - 1997
VL - 17
IS - 1
SP - 95
EP - 102
AB - 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.
LA - eng
KW - linear forest; bipartition; planar graphs; outerplanar graph; internal vertices; embedding; plane graph
UR - http://eudml.org/doc/270623
ER -
References
top- [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. Zbl0742.05041
- [5] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [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. Zbl0705.05016
- [8] J. Wang, On point-linear arboricity of planar graphs, Discrete Math. 72 (1988) 381-384, doi: 10.1016/0012-365X(88)90229-4. Zbl0665.05010
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.