Premium
On graphs with strongly independent color‐classes
Author(s) -
Gyárfás A.,
Jensen T.,
Stiebitz M.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10165
Subject(s) - mathematics , combinatorics , chromatic scale , graph , discrete mathematics , friendship graph , windmill graph , line graph , graph power
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