| Abstract: | 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 , for which χ* = m/n and η*(G)/χ*(G) is unbounded above. We investigate particular classes of these graphs and show that η* = 3 and η* = 4; (n ≥ 1), and η* = m - 2; (m ≥ 4). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 137–145, 1997 |
