✦ LIBER ✦

On linear vertex-arboricity of complementary graphs

✍ Scribed by Yousef Alavi; Jiuqiang Liu; Jianfang Wang

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 323 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180309

No coin nor oath required. For personal study only.

✦ Synopsis

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 linear vertex‐arboricities of a graph and its complement. Specifically, we prove that for any graph G of order p.

magnified image and for any graph G of order p = (2__n__ + 1)^2^, where n ≅ Z^+^, 2__n__ + 2 ≦ ρ(G) + ρ(G).

📜 SIMILAR VOLUMES

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 👁 1 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 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 ∆ =

List strong linear 2-arboricity of spars

List strong linear 2-arboricity of sparse graphs

✍ Oleg V. Borodin; Anna O. Ivanova 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

An inequality involving the vertex arbor

An inequality involving the vertex arboricity and edge arboricity of a graph

✍ Stefan A. Burr 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

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

## 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

Note on vertex degrees of planar graphs

✍ Miroslaw Truszczyáski 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB