Partitions of some planar graphs into two linear forests

• Volume: 17, Issue: 1, page 95-102
• ISSN: 2083-5892

top

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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.