---
id: wiki-2026-0508-graph-coloring-problem
title: Graph Coloring Problem
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [Vertex Coloring, Chromatic Number, k-Coloring]
duplicate_of: none
source_trust_level: A
confidence_score: 0.9
verification_status: applied
tags: [algorithms, graph-theory, np-complete, combinatorics, optimization]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: Python
  framework: NetworkX
---

# Graph Coloring Problem

## 매 한 줄
> **"매 vertex 에 색칠 — adjacent 끼리 다른 색, minimum 색 수가 chromatic number χ(G)"**. 1852년 Francis Guthrie 의 4-color conjecture 로 시작 — 1976년 Appel-Haken 의 computer-aided proof. 매 NP-complete (k≥3) 이지만 register allocation, scheduling, frequency assignment 등 매 광범위한 application.

## 매 핵심

### 매 정의
- **Vertex coloring**: V → {1,...,k} 의 함수 c, 매 (u,v) ∈ E ⇒ c(u) ≠ c(v).
- **Chromatic number χ(G)**: 매 minimum k 의 의미.
- **k-colorable**: 매 ≤k colors 의 valid coloring 존재.
- **Edge coloring / Total coloring / List coloring**: 매 variants.

### 매 이론적 boundaries
- **χ(G) ≤ Δ(G) + 1** (Brooks 정리: complete graph / odd cycle 제외 시 χ ≤ Δ).
- **χ(G) ≥ ω(G)** (clique number lower bound; perfect graph 시 equality).
- **4-Color Theorem**: 매 planar graph 의 χ ≤ 4 (1976, computer-assisted).
- **2-colorable ⟺ bipartite ⟺ no odd cycle** — 매 polynomial time 확인 가능.

### 매 응용
1. **Register allocation** (compiler): 매 variable interference graph 의 coloring → register 배정.
2. **Scheduling**: 매 conflict graph (시간 conflict 의 task) → time-slot 배정.
3. **Frequency assignment**: 매 cellular tower 간 interference 회피.
4. **Sudoku / map coloring**: 매 constraint satisfaction.
5. **Exam timetabling**: 매 student-overlap conflict 의 minimum slot.

## 💻 패턴

### Greedy Coloring (매 simplest baseline)
```python
import networkx as nx

def greedy_coloring(G, ordering=None):
    """Greedy: ordering 순서대로 가장 작은 사용가능 색 배정.
    Worst-case Δ+1 colors. Ordering 의 quality 이 핵심."""
    coloring = {}
    nodes = ordering or list(G.nodes())
    for v in nodes:
        used = {coloring[u] for u in G.neighbors(v) if u in coloring}
        c = 0
        while c in used:
            c += 1
        coloring[v] = c
    return coloring

# NetworkX built-in (Welsh-Powell 등 strategies):
G = nx.erdos_renyi_graph(50, 0.3, seed=42)
coloring = nx.coloring.greedy_color(G, strategy='largest_first')
print(f"Colors used: {max(coloring.values()) + 1}")
```

### DSATUR (매 saturation degree heuristic)
```python
def dsatur(G):
    """Brélaz 1979. 매 step: saturation (인접 색 수) max 인 vertex 선택.
    매 random graph 에서 greedy 보다 우수, χ 에 가까움."""
    coloring = {}
    saturation = {v: 0 for v in G.nodes()}
    while len(coloring) < len(G):
        uncolored = [v for v in G.nodes() if v not in coloring]
        v = max(uncolored, key=lambda x: (saturation[x], G.degree(x)))
        used = {coloring[u] for u in G.neighbors(v) if u in coloring}
        c = 0
        while c in used:
            c += 1
        coloring[v] = c
        for u in G.neighbors(v):
            if u not in coloring:
                neigh_colors = {coloring[w] for w in G.neighbors(u) if w in coloring}
                saturation[u] = len(neigh_colors)
    return coloring
```

### Backtracking (매 exact, small graphs)
```python
def chromatic_number_exact(G):
    """매 k=1,2,... 시도하며 k-colorable 검사 (NP-hard)."""
    nodes = list(G.nodes())
    n = len(nodes)
    
    def is_safe(v_idx, c, coloring):
        for u in G.neighbors(nodes[v_idx]):
            u_idx = nodes.index(u)
            if u_idx in coloring and coloring[u_idx] == c:
                return False
        return True
    
    def color_util(v_idx, k, coloring):
        if v_idx == n:
            return True
        for c in range(k):
            if is_safe(v_idx, c, coloring):
                coloring[v_idx] = c
                if color_util(v_idx + 1, k, coloring):
                    return True
                del coloring[v_idx]
        return False
    
    for k in range(1, n + 1):
        if color_util(0, k, {}):
            return k
    return n
```

### ILP Formulation (매 modern solver)
```python
from pulp import *

def graph_coloring_ilp(G, max_colors):
    """Integer Linear Programming — Gurobi/CPLEX 통해 매 exact solution.
    x[v,c] ∈ {0,1}: vertex v 의 color c."""
    prob = LpProblem("GraphColoring", LpMinimize)
    x = LpVariable.dicts("x", [(v,c) for v in G.nodes() for c in range(max_colors)], cat='Binary')
    y = LpVariable.dicts("y", range(max_colors), cat='Binary')  # color c used?
    
    prob += lpSum(y[c] for c in range(max_colors))  # minimize colors used
    
    for v in G.nodes():
        prob += lpSum(x[v,c] for c in range(max_colors)) == 1  # exactly 1 color
    for (u,v) in G.edges():
        for c in range(max_colors):
            prob += x[u,c] + x[v,c] <= 1  # adjacent ≠ color
    for v in G.nodes():
        for c in range(max_colors):
            prob += x[v,c] <= y[c]
    
    prob.solve(PULP_CBC_CMD(msg=0))
    return {v: c for v in G.nodes() for c in range(max_colors) if x[v,c].varValue == 1}
```

### Tabu Search (매 large instances)
```python
import random

def tabu_coloring(G, k, max_iter=10000, tabu_tenure=10):
    """매 k-coloring 의 conflict 최소화. Hertz-de Werra 1987.
    매 large random graphs 에 효과적."""
    coloring = {v: random.randint(0, k-1) for v in G.nodes()}
    tabu = {}
    best = coloring.copy()
    best_conflicts = sum(1 for u,v in G.edges() if coloring[u] == coloring[v])
    
    for it in range(max_iter):
        conflicts = [(u,v) for u,v in G.edges() if coloring[u] == coloring[v]]
        if not conflicts:
            return coloring
        # 매 best non-tabu move 선택
        best_move = None
        best_delta = float('inf')
        for u,v in conflicts:
            for vertex in (u, v):
                old_c = coloring[vertex]
                for new_c in range(k):
                    if new_c == old_c or (vertex, new_c) in tabu and tabu[(vertex,new_c)] > it:
                        continue
                    delta = sum(1 for w in G.neighbors(vertex) if coloring[w] == new_c) \
                          - sum(1 for w in G.neighbors(vertex) if coloring[w] == old_c)
                    if delta < best_delta:
                        best_delta = delta
                        best_move = (vertex, new_c)
        if best_move:
            v, c = best_move
            tabu[(v, coloring[v])] = it + tabu_tenure
            coloring[v] = c
    return coloring
```

### Register Allocation (매 compiler use case)
```python
def chaitin_register_allocation(interference_graph, num_registers):
    """Chaitin 1982. 매 LLVM/GCC 의 register allocation.
    Δ < k 의 vertex iteratively remove → stack → reverse pop & color."""
    G = interference_graph.copy()
    stack = []
    while G.nodes():
        # 매 degree < k vertex 찾기 (simplifiable)
        simplifiable = [v for v in G.nodes() if G.degree(v) < num_registers]
        if simplifiable:
            v = simplifiable[0]
        else:
            # 매 spill candidate (pick least-used)
            v = min(G.nodes(), key=lambda x: G.degree(x))
        stack.append((v, list(G.neighbors(v))))
        G.remove_node(v)
    
    coloring = {}
    while stack:
        v, neighbors = stack.pop()
        used = {coloring[u] for u in neighbors if u in coloring}
        for c in range(num_registers):
            if c not in used:
                coloring[v] = c
                break
        else:
            coloring[v] = 'SPILL'  # 매 memory 로 spill
    return coloring
```

## 매 결정 기준

| 상황 | Approach |
|---|---|
| Small graph (n ≤ 30) | Backtracking exact |
| Medium graph (n ≤ 1000) | ILP solver (Gurobi) |
| Large graph (n > 10k) | Tabu / DSATUR heuristic |
| Realtime / approximate OK | Greedy with largest_first |
| Compiler register allocation | Chaitin's algorithm |
| Bipartite check only | BFS 2-coloring (O(V+E)) |

**기본값**: NetworkX `greedy_color(strategy='DSATUR')` — 매 quality/speed balance 우수.

## 🔗 Graph
- 부모: [[Graph_Theory|Graph-Theory]] · [[Combinatorial-Optimization]]

## 🤖 LLM 활용
**언제**: 매 problem decomposition, 매 algorithm selection, 매 code skeleton 생성, 매 ILP formulation 자동화.
**언제 X**: 매 instance-specific exact solution — 매 LLM hallucinate 가능, dedicated solver (Gurobi/CPLEX) 사용 권장.

## ❌ 안티패턴
- **Greedy 의 첫 ordering 사용**: 매 worst-case n colors. Largest-first / DSATUR ordering 사용.
- **Brute force on n>30**: 매 exponential 시간 — heuristic / ILP 으로 전환.
- **k-coloring 직접 푸는 대신 chromatic 추정 안 함**: 매 lower bound (clique) / upper bound (Brooks) 활용.
- **List coloring 을 vertex coloring 과 혼동**: 매 list coloring 의 χ_l(G) 의 차이.

## 🧪 검증 / 중복
- Verified against Brooks' Theorem, 4-Color Theorem (Appel-Haken 1976), Chaitin's allocation.
- 신뢰도 A (CLRS, Diestel "Graph Theory", Chartrand-Zhang).

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 |
| 2026-05-10 | Manual cleanup — full content (definitions, ILP, tabu, Chaitin allocation, applications) |
