✦ LIBER ✦

The star arboricity of graphs

✍ Scribed by I. Algor; N. Alon

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 714 KB
Volume: 75
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90073-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The star-arboricity of the complete regu

The star-arboricity of the complete regular multipartite graphs

✍ Yasukazu Aoki 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 331 KB

A subgraph H of a graph G is called a star-subgraph if each component of H is a star. The star-arboricify of G, denoted by sa(G), is the minimum number of star-subgraphs that partition the edges of G. In this paper we show that sa(G) is [r/21 + 1 or [r/2] + 2 for the complete r-regular multipartite

Star arboricity of graphs

✍ S.L. Hakimi; J. Mitchem; E. Schmeichel 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 279 KB

We develop a connection between vertex coloring in graphs and star arboricity which allows us to prove that every planar graph has star arboricity at most 5. This settles an open problem raised independently by Algor and Alon and by Ringel. We also show that deciding if a graph has star arboricity 2

On incidence coloring and star arboricit

On incidence coloring and star arboricity of graphs

✍ Barry Guiduli 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 190 KB

In this note we show that the concept of incidence coloring introduced by Brualdi and Massey [4] is a special case of directed star arboricity, introduced by Agor and Alon ['2]. A conjecture in [4] concerning asymptotics of the incidence coloring number is solved in the negative following an example

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

The linear arboricity of some regular gr

The linear arboricity of some regular graphs

✍ Hikoe Enomoto; Bernard Péroche 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 582 KB

W e prove that the linear arboricity of every 5-regular graph is 3. That is, the edges of any 5-regular graph are covered by three linear forests. W e also determine the linear arboricity of 6-regular graphs and 8-regular graphs. These results improve the known upper bounds for the linear arboricity

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 __