  We study the chromatic number of the curve graph of a surface. We show that
the chromatic number grows like k log k for the graph of separating curves on a
surface of Euler characteristic -k. We also show that the graph of curves that
represent a fixed non-zero homology class is uniquely t-colorable, where t
denotes its clique number. Together, these results lead to the best known
bounds on the chromatic number of the curve graph. We also study variations for
arc graphs and obtain exact results for surfaces of low complexity. Our
investigation leads to connections with Kneser graphs, the Johnson
homomorphism, and hyperbolic geometry.
