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

Abstract

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

How to cite

top

Piotr 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. [1] M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa International Publications, 1991) 41-68. 
  2. [2] P. Borowiecki, P-Bipartitions of Graphs, Vishwa International J. GraphTheory 2 (1993) 109-116. 
  3. [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. [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. [5] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  6. [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. [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. [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 ?

top

You must be logged in to post comments.