Graph Coloring

Graph	χ
Tree (২+ vertex)	2
Bipartite	2
জোড় cycle	2
বিজোড় cycle	3
Kₙ	n
Planar	≤ 4

χ(G) বের করা NP-complete — এমনকি χ ≤ 3 কি না সেটাও। তবু প্রতিদিন ব্যবহার হয়, heuristic দিয়ে।

সবচেয়ে বড় প্রয়োগ — register allocation:

• vertex = variable-এর live range
• edge = দুইটা একই সময়ে live (তাই একই register-এ যেতে পারে না)
• রঙ = CPU register

x86-64-এ মাত্র ১৬টা general purpose register। রঙ না পেলে variable spill হয় — memory-তে যায়, অনেক ধীর। Compiler প্রতিটা function-এ এই NP-complete সমস্যা heuristic দিয়ে সমাধান করে (Chaitin’s algorithm, linear scan)।

Greedy (Welsh–Powell) সর্বোচ্চ Δ+1 রঙ ব্যবহার করে (Δ = সর্বোচ্চ degree), আর প্রায়ই তার চেয়ে কম:

for v in sorted(adj, key=lambda v: -len(adj[v])):
    used = {color[u] for u in adj[v] if u in color}
    color[v] = next(c for c in count() if c not in used)

অন্য প্রয়োগ: exam scheduling, frequency assignment, Sudoku।