On graphs with strongly independent color‐classes

We prove that for every k there is a k ‐chromatic graph with a k ‐coloring where the neighbors of each color‐class form an independent set. This answers a question raised by N. J. A. Harvey and U. S. R. Murty [4]. In fact we find the smallest graph G k with the required property for every k . The graph G k exhibits remarkable similarity to Kneser graphs. The proof that G k is k ‐chromatic relies on Lovász's theorem about the chromatic number of graphs with highly connected neighborhood complexes. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 1–14, 2004