𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounds for the vertex linear arboricity

✍ Scribed by Makoto Matsumoto

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
351 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The vertex linear arboricity vla(G) of a nonempty graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph whose connected components are paths. This paper provides an upper bound for vla(G) of a connected nonempty graph G, namely vla(G) ≦ 1 + ⌊δ(G)/2βŒ‹ where Ξ΄(G) denotes the maximum degree of G. Moreover, if Ξ΄(G) is even, then vla(G) = 1 + ⌊δ(G)/2βŒ‹ if and only if G is either a cycle or a complete graph.

πŸ“œ SIMILAR VOLUMES

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

Upper bound for linear arboricity
Upper bound for linear arboricity
✍ Paul C. Kainen πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 264 KB

Using the K&&Hall Theorem, we establish the Akiyama-Exoo-Harary Conjecture up to an additive factor which is at most linear in the square root of the graph's topological genus.

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.

Linear arboricity for graphs with multip
Linear arboricity for graphs with multiple edges
✍ Houria AΓ―t-djafer πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 266 KB

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree A(G). the linear arboricity / a ( G ) satisfies rA(G)/21 5 /a(G) 5 r(A(G) + 11/21, Here it is proved that if G is a loopless graph with maximum degree A ( G ) S k and maximum edge multiplicity ## 1. Introduction

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 βˆ† =