The assignment of colors to elements of a graph where adjacent elements must not share the same color.
Four-Color Theorem
Any planar graph can be colored with at most 4 colors. Other direction is not true.
Algorithms
Greedy algorithm give a valid coloring by making local-optimal choices at each step. But not globally optimal.
Heuristic based algorithms improve quality of the solution (low number of colors). Optimal solutions become harder for large graphs. Exact solutions are computationally expensive.