2, since the graph is bipartite. One color for the top set of vertices, another color for the bottom set of vertices.