9.20 Graph Coloring Basics

Problem

You need to assign labels, colors, or resources to vertices so that adjacent vertices do not conflict.

Many problems involve incompatibility:

A meeting cannot use the same room as an overlapping meeting. Two neighboring regions on a map should not use the same color. Two variables that are live at the same time should not use the same register. Two exams taken by the same student should not be scheduled in the same time slot.

You need a way to model and solve conflict assignment problems.

Solution

Use graph coloring.

In vertex coloring, each vertex receives a color. Adjacent vertices must receive different colors.

Consider:

A -- B
|    |
D -- C

A valid coloring is:

A = Red
B = Blue
C = Red
D = Blue

No edge connects two vertices with the same color.

The colors are abstract. They may represent time slots, rooms, registers, channels, teams, or categories.

Discussion

Graph coloring is a general model for resource assignment under constraints.

The graph captures conflicts:

Problem	Vertex	Edge	Color
Exam scheduling	Exam	Same student takes both	Time slot
Register allocation	Variable	Live at same time	Machine register
Map coloring	Region	Shared border	Map color
Wireless networks	Transmitter	Interference	Frequency channel
Task assignment	Task	Cannot run together	Worker or batch

Once the conflict graph is built, coloring asks:

How many colors are needed?

or:

Can this graph be colored with k colors?

The smallest possible number of colors is called the chromatic number.

Two-Coloring

The simplest useful case is two-coloring.

A graph is two-colorable exactly when it is bipartite.

Example:

A -- B -- C -- D

Valid coloring:

A = 0
B = 1
C = 0
D = 1

This is the same BFS or DFS coloring technique from Section 9.14.

from collections import deque

def two_color(graph):
    color = {}

    for start in graph:
        if start in color:
            continue

        color[start] = 0
        queue = deque([start])

        while queue:
            vertex = queue.popleft()

            for neighbor in graph[vertex]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[vertex]
                    queue.append(neighbor)
                elif color[neighbor] == color[vertex]:
                    return None

    return color

If the function returns None, the graph cannot be colored with two colors.

Greedy Coloring

For more than two colors, a common practical approach is greedy coloring.

Process vertices one at a time. Assign each vertex the smallest color not already used by its neighbors.

def greedy_coloring(graph):
    color = {}

    for vertex in graph:
        used = {
            color[neighbor]
            for neighbor in graph[vertex]
            if neighbor in color
        }

        c = 0

        while c in used:
            c += 1

        color[vertex] = c

    return color

Example:

graph = {
    "A": ["B", "C"],
    "B": ["A", "C"],
    "C": ["A", "B"],
}

Output:

{
    "A": 0,
    "B": 1,
    "C": 2,
}

A triangle requires three colors because every vertex touches every other vertex.

Vertex Order Matters

Greedy coloring is fast, but the result depends on vertex order.

Consider the same graph processed in a different order. The algorithm may use more colors than necessary.

This is the main weakness of greedy coloring. It produces a valid coloring, but not necessarily an optimal one.

A common improvement is to process high-degree vertices first.

def greedy_coloring_by_degree(graph):
    order = sorted(
        graph,
        key=lambda vertex: len(graph[vertex]),
        reverse=True
    )

    color = {}

    for vertex in order:
        used = {
            color[neighbor]
            for neighbor in graph[vertex]
            if neighbor in color
        }

        c = 0

        while c in used:
            c += 1

        color[vertex] = c

    return color

This heuristic often performs well in practice, though it still does not guarantee the minimum number of colors.

Checking a Coloring

A coloring is valid if every edge connects vertices with different colors.

def is_valid_coloring(graph, color):
    for vertex in graph:
        if vertex not in color:
            return False

        for neighbor in graph[vertex]:
            if color[vertex] == color[neighbor]:
                return False

    return True

Example:

color = {
    "A": 0,
    "B": 1,
    "C": 0,
}

print(is_valid_coloring(graph, color))

This validation step is useful when testing heuristics or external solvers.

Coloring with k Colors

Sometimes the number of available colors is fixed.

For example, a scheduler may have exactly three time slots.

The question becomes:

Can this graph be colored with k colors?

A backtracking solver is direct.

def color_with_k(graph, k):
    vertices = list(graph)
    color = {}

    def search(index):
        if index == len(vertices):
            return dict(color)

        vertex = vertices[index]

        for c in range(k):
            conflict = False

            for neighbor in graph[vertex]:
                if color.get(neighbor) == c:
                    conflict = True
                    break

            if conflict:
                continue

            color[vertex] = c

            result = search(index + 1)

            if result is not None:
                return result

            del color[vertex]

        return None

    return search(0)

This version is exponential in the worst case, but it is easy to understand and works well for small graphs.

Example: Scheduling Exams

Suppose exams conflict when at least one student must take both.

graph = {
    "Algorithms": ["Databases", "Networks"],
    "Databases": ["Algorithms", "Compilers"],
    "Networks": ["Algorithms"],
    "Compilers": ["Databases"],
}

A coloring might be:

{
    "Algorithms": 0,
    "Databases": 1,
    "Networks": 1,
    "Compilers": 0,
}

Interpreting colors as time slots:

Slot 0: Algorithms, Compilers
Slot 1: Databases, Networks

No student has two conflicting exams in the same slot.

Complete Graphs

A complete graph with n vertices requires n colors.

Every vertex is adjacent to every other vertex.

A -- B
|\  /|
| \/ |
| /\ |
|/  \|
C -- D

For four vertices, each vertex needs a distinct color.

This gives a useful upper bound example: dense conflict graphs can require many resources.

Planar Graph Note

Map coloring is a famous graph-coloring application.

When regions of a map are converted into a graph, each region becomes a vertex, and shared borders become edges.

The Four Color Theorem states that every planar map can be colored with at most four colors.

This is a deep theorem, not an algorithmic shortcut for every practical coloring problem. It applies only to planar graphs and specific map-style adjacency.

Complexity Analysis

Let:

Operation	Complexity
Validate coloring	O(V + E)
Greedy coloring	O(V + E) with set-based neighbor checks
Degree sorting	O(V log V)
Two-coloring	O(V + E)
Exact k-coloring	Exponential worst case

Graph coloring is easy to validate but hard to optimize.

Finding the minimum number of colors for an arbitrary graph is computationally difficult. Practical systems usually use heuristics, approximations, or domain-specific structure.

Common Pitfalls

Do not confuse graph coloring with connected-component labeling. Components may reuse colors.

Do not assume greedy coloring is optimal.

Do not ignore vertex ordering. It can change the number of colors used.

Do not model resources as vertices unless the conflict relationship belongs there. Usually the conflicting items are vertices, and resources are colors.

Do not forget self-loops. A vertex with an edge to itself cannot be colored validly, because it would need a color different from itself.

Do not assume two-coloring works unless the graph is bipartite.

Takeaway

Graph coloring assigns colors to vertices so that adjacent vertices receive different colors. It models resource allocation under conflict constraints, including scheduling, register allocation, map coloring, channel assignment, and batching. Two-coloring is equivalent to bipartite testing and can be solved in linear time. General coloring is much harder, so practical solutions often use greedy heuristics, ordering strategies, or backtracking for small instances.