✦ LIBER ✦

Star arboricity of graphs

✍ Scribed by S.L. Hakimi; J. Mitchem; E. Schmeichel

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 279 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00313-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 is NP-complete, even for 2-degenerate graphs.

The notation of star coloring was first defined in [1], where the following was established.

Star coloring of balanced, complete multipartite graphs was considered in [4,7]. Let Kn®p denote the complete p-partite graphs with n vertices in each partite set. The following bounds were obtained in [4].

📜 SIMILAR VOLUMES

The star arboricity of graphs

✍ I. Algor; N. Alon 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 714 KB

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

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

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 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 point-linear arboricity of planar gra

On point-linear arboricity of planar graphs

✍ Jianfang Wang 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 220 KB

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 follow