Chromatic numbers of Knesertype graphs Abstract   Let    G  (  n  ,  r  ,  s  )    be a graph whose vertices are all relement subsets of an nelement set, in which two vertices are adjacent if they intersect in exactly s elements. In this paper we study chromatic numbers of    G  (  n  ,  r  ,  s  )    with    r  ,  s    being fixed constants and n tending to infinity. Using a recent result of Keevash on existence of designs we deduce an inequality    xcfx87  (  G  (  n  ,  r  ,  s  )  )  xe2xa9xbd  (  1    o  (  1  )  )    n    r  xe2x88x92  s      (  r  xe2x88x92  s  xe2x88x92  1  )  !    (  2  r  xe2x88x92  2  s  xe2x88x92  1  )  !      for    r  u003e  s    with    r  ,  s    fixed constants. This inequality gives sharp upper bounds for    r  xe2xa9xbd  2  s    1   . Also we develop an elementary approach to this problem and prove that    xcfx87  (  G  (  n  ,  4  ,  2  )  )  xe2x88xbc      n    2      6      without use of Keevashu0027s results.  Some bounds on the list chromatic number of    G  (  n  ,  r  ,  s  )    are also obtained.

The Hardness of 3Uniform Hypergraph Coloring We prove that coloring a 3uniform 2colorable hypergraph with c colors is NPhard for any constant c. The best known algorithm 20 colors such a graph using O(n15) colors. Our result immediately implies that for any constants k xe2x89xa5 3 and c2 u003e c1 u003e 1, coloring a kuniform c1colorable hypergraph with c2 colors is NPhard; the case k  2, however, remains wide open.This is the first hardness result for approximatelycoloring a 3uniform hypergraph that is colorable with a constant number of colors. For k xe2x89xa5 4 such a result has been shown by 14, who also discussed the inherent difference between the k  3 case and k xe2x89xa5 4.Our proof presents a new connection between the LongCode and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph 19,22 and the Schrijver graph 26. We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has xe2x80x98manyxe2x80x99 nonmonochromatic edges.