Graph Coloring

Theorem 13.5.1. For n even, χ ′(Kn) = n−1, and for n odd, χ ′(Kn) = n.

Theorem 13.5.2. A graph G is bipartite if and only if is 2-vertex colorable.

Theorem 13.5.3. A graph G is bipartite ⇐⇒ G has no odd cycles.