Assign colors to graph vertices using a greedy algorithm, reporting the chromatic number upper bound.
Graph coloring assigns colors to vertices so that no two adjacent vertices share the same color. The greedy algorithm processes vertices in order and assigns the smallest available color. The result is an upper bound on the chromatic number (minimum colors needed).
Greedy: for each vertex v in order, assign the smallest color not used by any neighbor of v
No. Greedy gives an upper bound that depends on vertex ordering. The true chromatic number may be lower. Finding the exact chromatic number is NP-hard in general.
Scheduling (exams, tasks), register allocation in compilers, frequency assignment in telecommunications, and map coloring.