On graphs with strongly independent color‐classes
András Gyárfás, T. Jensen, Michael Stiebitz · Journal of Graph Theory · 2004
Abstract 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 Gk with the required property for every k. The graph Gk exhibits remarkable similarity to Kneser graphs. The proof that Gk 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