Name
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 |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1002/jgt.v46:1 | Journal of Graph Theory |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Comparability graph,Line graph,Forbidden graph characterization,Cograph,Kneser graph,1-planar graph,Universal graph,Mathematics,Split graph | Journal | 46 |
Issue | Citations | PageRank |
1 | 16 | 1.42 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| András Gyárfás | 1 | 582 | 102.26 |
| T. Jensen | 2 | 16 | 1.42 |
| Michael Stiebitz | 3 | 207 | 30.08 |