Course contentsShow
← Computer Science
Lesson 1925 of 2,87243. Complexity TheoryFree lesson

Graph Coloring Problem

Assigning colors to vertices so adjacent vertices differ, deciding if k colors suffice.

Graph Coloring Problem

What you'll learn: You'll understand how the graph coloring problem asks whether you can assign colors to vertices so that no two adjacent vertices share the same color using at most k colors.

The Core Idea

Imagine you're planning a schedule for exam periods. Some students are enrolled in multiple courses, so those courses can't have exams at the same time. If you represent courses as vertices and draw edges between courses that share students, the question becomes: can you assign time slots (colors) to courses so that no two connected courses get the same slot, using only k time slots?

That's the graph coloring problem: given a graph G and an integer k, can you assign one of k colors to each vertex such that no two adjacent vertices (connected by an edge) have the same color?

Why It's NP-Complete

Graph coloring is in NP because if someone gives you a coloring, you can quickly verify it works—just check every edge to ensure its endpoints have different colors. That's polynomial-time verification.

However, finding such a coloring (or proving none exists) appears to require trying many possibilities. The decision version—"Does a k-coloring exist?"—is NP-complete for k ≥ 3. This means if you could solve graph coloring efficiently, you could solve all NP problems efficiently.

Real-World Applications

Beyond exam scheduling, graph coloring appears in:

  • Register allocation in compilers (variables are vertices, conflicts are edges)
  • Frequency assignment in wireless networks (towers are vertices, interference creates edges)
  • Map coloring (regions are vertices, borders create edges)

Key Takeaway: The graph coloring problem asks if k colors suffice to color vertices so adjacent ones differ—a classic NP-complete problem with surprising practical relevance in scheduling, resource allocation, and optimization.