✦ LIBER ✦

Acyclic graph coloring and the complexity of the star chromatic number

✍ Scribed by David R. Guichard

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 294 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170202

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Star chromatic number, introduced by A. Vince, is a natural generalization of chromatic number. We consider the question, “When is χ* < χ?” We show that χ* < χ if and only if a particular digraph is acyclic and that the decisioin problem associated with this question is probably not in NP though it is both NP‐hard and NP‐easy. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

The star chromatic number of a graph

✍ H. L. Abbott; B. Zhou 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 469 KB 👁 2 views

## Abstract We study a generalization of the notion of the chromatic number of a graph in which the colors assigned to adjacent vertices are required to be, in a certain sense, far apart. © 1993 John Wiley & Sons, Inc.

Acyclic and oriented chromatic numbers o

Acyclic and oriented chromatic numbers of graphs

✍ Kostochka, A. V.; Sopena, E.; Zhu, X. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB 👁 2 views

The oriented chromatic number χ o ( G) of an oriented graph G = (V, A) is the minimum number of vertices in an oriented graph H for which there exists a homomorphism of G to H. The oriented chromatic number χ o (G) of an undirected graph G is the maximum of the oriented chromatic numbers of all the

The star-chromatic number of planar grap

The star-chromatic number of planar graphs

✍ Moser, David 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 2 views

The star-chromatic number of a graph, a parameter introduced by Vince, is a natural generalization of the chromatic number of a graph. Here we construct planar graphs with star-chromatic number r, where r is any rational number between 2 and 3, partially answering a question of Vince.

The generalized acyclic edge chromatic n

The generalized acyclic edge chromatic number of random regular graphs

✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

The Signed Chromatic Number of the Proje

The Signed Chromatic Number of the Projective Plane and Klein Bottle and Antipodal Graph Coloring

✍ T. Zaslavsky 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 440 KB

Some Theorems Concerning the Star Chroma

Some Theorems Concerning the Star Chromatic Number of a Graph

✍ Bing Zhou 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 379 KB

We investigate the notion of the star chromatic number of a graph in conjunction with various other graph parameters, among them, clique number, girth, and independence number. 1997 Academic Press /\*(G)=inf { m d : G has an (m, d )&coloring = . article no. TB961738 245 0095-8956Â97 25.00