✦ LIBER ✦

Multichromatic numbers, star chromatic numbers and Kneser graphs

✍ Scribed by Johnson, A.; Holroyd, F. C.; Stahl, S.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 126 KB
Volume: 26
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199711)26:3<137::aid-jgt4>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

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 cycle or a complete graph. We show that χ * (G) ≤ η * (G) for any finite simple graph G. We consider the Kneser graphs G m n , for which χ * (G m n ) = m/n and η * (G)/χ * (G) is unbounded above. We investigate particular classes of these graphs and show that η * (G 2n+1 n ) = 3 and η * (G 2n+2 n ) = 4 (n ≥ 1), and η * (G m 2 ) = m -2 (m ≥ 4).

📜 SIMILAR VOLUMES

Star chromatic numbers of some planar gr

Star chromatic numbers of some planar graphs

✍ Gao, Guogang; Wang, Yiju; Zhou, Huishan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB 👁 1 views

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 pla

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.

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

Rank and chromatic number of a graph

✍ Kotlov, Andrei? 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 1 views

It was proved (A. Kotlov and L. Lovász, The rank and size of graphs, J. Graph Theory 23 (1996), 185-189) that the number of vertices in a twin-free graph is O(( √ 2) r ) where r is the rank of the adjacency matrix. This bound was shown to be tight. We show that the chromatic number of a graph is o(∆

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