✦ LIBER ✦

On incidence coloring and star arboricity of graphs

✍ Scribed by Barry Guiduli

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 190 KB
Volume: 163
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00342-t

No coin nor oath required. For personal study only.

✦ Synopsis

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 in [2]. We generalize a result in [3] concerning the star arboricity of graphs to the directed case by a slight modification of their proof, to give the same asymptotic bound as in the undirected case. As a result, we get tight asymptotic bounds for the maximum incidence coloring number of a graph in terms of its degree.

📜 SIMILAR VOLUMES

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

The star arboricity of graphs

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

Star coloring of graphs

✍ Guillaume Fertin; André Raspaud; Bruce Reed 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract A __star coloring__ of an undirected graph __G__ is a proper vertex coloring of __G__ (i.e., no two neighbors are assigned the same color) such that any path of length 3 in __G__ is not bicolored. The __star chromatic number__ of an undirected graph __G__, denoted by χ~s~(__G__), is the

Star coloring of sparse graphs

✍ Yuehua Bu; Daniel W. Cranston; Mickaël Montassier; André Raspaud; Weifan Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract A proper coloring of the vertices of a graph is called a __star coloring__ if the union of every two color classes induces a star forest. The star chromatic number χ~__s__~(__G__) is the smallest number of colors required to obtain a star coloring of __G__. In this paper, we study the r

Star coloring bipartite planar graphs

✍ H. A. Kierstead; André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eig

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