Graph coloring

The chromatic number \(\chi(G)\) is the least \(k\) for which a proper coloring exists. We have \(\chi(G)=1\) only when there are no edges, and \(\chi(G)=2\) exactly when \(G\) has edges and is bipartite. In \(K_n\) all vertices are adjacent, so \(\chi(K_n)=n\); for a cycle, \(\chi(C_n)=2\) if \(n\) is even and \(3\) if it is odd.

Two observations give bounds. If \(G\) contains a complete subgraph \(K_r\), then \(\chi(G)\ge r\), because those \(r\) vertices use distinct colors. And if \(\Delta\) is the maximum degree, a greedy coloring (coloring vertices one by one with a free color) uses at most \(\Delta+1\) colors, since each vertex has at most \(\Delta\) already colored neighbors. Brooks' theorem sharpens this: except for complete graphs and odd cycles, \(\Delta\) colors suffice.

A guiding example is exam scheduling: courses are vertices, there is an edge when they share students, and each color is a time slot; \(\chi(G)\) is the least number of clash-free slots. A common mistake is to think greedy coloring always gives the minimum: it depends on the vertex order, and finding \(\chi(G)\) is hard in general. The famous four color theorem states that every planar graph can be colored with 4 colors.