2004/03/11 by András Gyárfás, Torben R. Jensen, Michael Stiebitz · 1 citation
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Mathematics #Combinatorics #Chromatic scale #Graph #Discrete mathematics #Friendship graph #Windmill graph #Line graph #Graph power
paper · doi:10.1002/jgt.10165
openalex publication_date 2004/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
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 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