> The Bipartite graph class is also a bit silly in this case, since it's by definition the 2-colorable graphs

Be a little bit careful here: another common textbook definitions of bipartite graphs are:

- a graph is bipartite iff it has no odd circle.

- (for people who are into algebraic/spectral graph theory :-) ) a graph is bipartite iff its spectrum is symmetric.

I personally like the latter two definitions because the "normal" definition of a bipartite graph suggests that

1-colorable, 2-colorable, 3-colorable, 4-colorable, ...

graphs are conceptually very "similar" (k-colorable with different values for k).

But we now that it is very easy (i.e. there exists a polynomial-time algorithm) to decide if a graph is 1- or 2-colorable, but from k=3 on, it is NP-complete to decide whether a given graph is k-colorable.

Using one of these alternative definitions (and then showing "a graph is bipartite iff it is 2-colorable" as a lemma/theorem) makes it very clear that from a complexity point being 1- or 2-colorable is (assuming P != NP) something very different from being k-colorable for k >= 3.