𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On point-linear arboricity of planar graphs

✍ Scribed by Jianfang Wang

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
220 KB
Volume
72
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The point-linear arboricity of a graph G = (V, E), written as p,(G), is defined as p,(G) =min{k / there exists a partition of V into k subsets, V =LJt, V,, such that (V,) is a linear forest for 1 <i <k}.

In this paper, we will discuss the point-linear arboricity of planar graphs and obtained following results: p,,(G) = 2 if G is a outplanar graph. p,,(G) = 4 if G is a planar graph.

📜 SIMILAR VOLUMES

On the linear arboricity of planar graph
On the linear arboricity of planar graphs
✍ Wu, Jian-Liang 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 2 views

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. Akiyama, Exoo, and Harary conjectured for any simple graph G with maximum degree ∆. The conjecture has been proved to be true for graphs having ∆ =

On the linear vertex-arboricity of a pla
On the linear vertex-arboricity of a planar graph
✍ K. S. Poh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

## Abstract We prove in this note that the linear vertex‐arboricity of any planar graph is at most three, which confirms a conjecture due to Broere and Mynhardt, and others.

On the critical point-arboricity graphs
On the critical point-arboricity graphs
✍ Riste Škrekovski 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of __k__‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph __G__ embedded on a surface __S__ with Euler genus __

On linear vertex-arboricity of complemen
On linear vertex-arboricity of complementary graphs
✍ Yousef Alavi; Jiuqiang Liu; Jianfang Wang 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 323 KB 👁 1 views

## Abstract The linear vertex‐arboricity ρ(__G__) of a graph __G__ is defined to be the minimum number of subsets into which the vertex set of __G__ can be partitioned such that each subset induces a linear forest. In this paper, we give the sharp upper and lower bounds for the sum and product of l

On the linear k-arboricity of cubic grap
On the linear k-arboricity of cubic graphs
✍ Bill Jackson; Nicholas C. Wormald 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 231 KB

Bermond et al. [2] conjectured that the edge set of a cubic graph G can be partitioned into two k-linear forests, that is to say two forests whose connected components are paths of length at most k, for all k >/5. We shall prove a weaker result that the statement is valid for all k/> 18. All graphs

The linear arboricity of planar graphs o
The linear arboricity of planar graphs of maximum degree seven is four
✍ Jian-Liang Wu; Yu-Wen Wu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB 👁 2 views

## Abstract The linear arboricity of a graph __G__ is the minimum number of linear forests which partition the edges of __G__. Akiyama et al. conjectured that $\lceil {\Delta {({G})}\over {2}}\rceil \leq {la}({G}) \leq \lceil {\Delta({G})+{1}\over {2}}\rceil$ for any simple graph __G__. Wu wu prove