Multichromatic numbers, star chromatic numbers and Kneser graphs

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 chi* and eta*, the work of the above authors shows that chi*(G) = eta*(G) if G is bipartite, an odd cycle or a complete graph. We show that chi*(G) equal to or less than eta*(G) for any finite simple graph G. We consider the Kneser graphs G(n)(m), for which chi*(G(n)(m)) = m/n and eta*(G)/X*(G) is unbounded above. We investigate particular classes of these graphs and show that eta*(G(n)(2n+1)) = 3 and eta*(G(n)(2n+2)) = 4 (n > 1), and eta*(G(2)(m)) = m - 2 (m equal to or greater than 4). (C) 1997 John Wiley & Sons, Inc.