We present a novel family of simplicial complexes associated with the graph coloring problem. They include many well-known simplicial complexes such as chessboard complexes and crosspolytopes. We then study conditions under which these complexes become vertex decomposable and hence shellable. The connectivity of these complexes is also investigated. We apply these results to Tverberg's theorem with constraints and also to the chromatic number of certain Kneser-type hypergraphs and improve upon existing facts. Notably, we prove a conjecture of Engström and Norén on Tverberg graphs.