On multichromatic numbers of widely colorable graphs

A coloring is called s ‐wide if no walk of length 2 s − 1 connects vertices of the same color. A graph is s ‐widely colorable with t colors if and only if it admits a homomorphism into a universal graph W ( s , t ) . Tardif observed that the value of the r th multichromatic number χ r ( W ( s , t ) ) of these graphs is at least t + 2 ( r − 1 ) and equality holds for r = s = 2 . He asked whether there is equality also for r = s = 3 . We show that χ s ( W ( s , t ) ) = t + 2 ( s − 1 ) for all s thereby answering Tardif's question. We observe that for large r (with respect to s and t fixed) we cannot have equality and that for s fixed and t going to infinity the fractional chromatic number of W ( s , t ) also tends to infinity. The latter is a simple consequence of another result of Tardif on the fractional chromatic number of generalized Mycielski graphs.