Premium
Multichromatic numbers, star chromatic numbers and Kneser graphs
Author(s) -
Johnson A.,
Holroyd F. C.,
Stahl S.
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199711)26:3<137::aid-jgt4>3.0.co;2-s
Subject(s) - combinatorics , mathematics , bipartite graph , chromatic scale , graph , discrete mathematics
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). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 137–145, 1997