✦ LIBER ✦

Star chromatic numbers of some planar graphs

✍ Scribed by Gao, Guogang; Wang, Yiju; Zhou, Huishan

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 173 KB
Volume: 27
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199801)27:1<33::aid-jgt6>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

The concept of the star chromatic number of a graph was introduced by Vince (A. Vince, Star chromatic number, J. Graph Theory 12 (1988), 551--559), which is a natural generalization of the chromatic number of a graph. This paper calculates the star chromatic numbers of three infinite families of planar graphs. More precisely, the first family of planar graphs has star chromatic numbers consisting of two alternating infinite decreasing sequences between 3 and 4; the second family of planar graphs has star chromatic numbers forming an infinite decreasing sequence between 3 and 4; and the third family of planar graphs has star chromatic number 7/2.

📜 SIMILAR VOLUMES

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.

Multichromatic numbers, star chromatic n

Multichromatic numbers, star chromatic numbers and Kneser graphs

✍ Johnson, A.; Holroyd, F. C.; Stahl, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

We investigate the relation between the multichromatic number (discussed by Stahl and by Hilton, Rado and Scott) and the star chromatic number (introduced by Vince) of a graph. Denoting these by χ \* and η \* , the work of the above authors shows that χ \* (G) = η \* (G) if G is bipartite, an odd cy

On the vertex face total chromatic numbe

On the vertex face total chromatic number of planar graphs

✍ Weifan, Wang; Jiazhuang, Liu 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB 👁 2 views

Let G be a planar graph. The vertex face total chromatic number ,y13(G) of G is the least number of colors assigned to V(G) U F(G) such that no adjacent or incident elements receive the same color. The main results of this paper are as follows: (1) We give the vertex face total chromatic number for

The chromatic number of oriented graphs

✍ Sopena, Eric 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 2 views

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with

Game chromatic number of outerplanar gra

Game chromatic number of outerplanar graphs

✍ Guan, D. J.; Zhu, Xuding 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 2 views

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs.

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 👁 1 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