## Graph Coloring

# Graph Coloring

**Bart Massey**

### More About Graphs

Degree of vertex: number of impinging edges

- D(G) = maximum degree of any vertex in V

Clique: Subset W of V such that for all v1, v2 in W, (v1, v2) in E

- w(G) = size of largest clique in G

Independent Set: Subset W of V such that for all v1, v2 in W, (v1, v2) not in E

k-Partite Graph: Can partition V into k subsets V1..Vk such that there exists no edge (v1, v2) in E such that v1 and v2 are in the same partition.

- bipartite: k = 2
- tripartite: k = 3

### Graph Families

Clique Dn

Cycle Cn

Star Sn

Wheel Wn

Line Ln

Forest, Tree

### Graph Coloring

Coloring is function f : V -> N+

By convention, f is compact on range: range(f) = {1..k} for some k

A legal coloring is a coloring such that for every edge (v1, v2) in E f(v1) <> f(v2)

Graphs can be partially colored: make f a partial function

Finds independent sets

- In fact, k-coloring finds k-partite sets

### Chromatic Number

Usually interested in finding smallest number of colors that will color a given graph

- Or testing whether graph can be colored with k colors

k = X(G) is the "chromatic number" of G: smallest number of colors that will work

### Applications

Applications are around avoiding forbidden sharing

Map coloring: Bordering states cannot have same color

Team formation: Incompatible people cannot be on same team

Register Allocation: Values in use at same time cannot be in same register

Scheduling: Tasks that depend on each other cannot be done at the same time

### Constraints on Chromatic Number

Obviously 2 <= X(G) <= |V| for non-trivial graphs

w(G) <= X(G) <= D(G) + 1

- Unless G is an odd cycle or a clique, X(G) <= D(G)

Proof that X(G) <= D(G) + 1

- Base Case: True for single vertex
- Inductive Case:
- G' = G \ ({v}, edges(v)) for some vertex v in V
- D(G') <= D(G)
- X(G') <= D(G') + 1 by induction
- Now reinsert v: since v could be connected to at most every vertex of G', then there must always be one free color of D(G) + 1 colors

See paper for other bounds

### Preconditioning Graphs For Coloring

Color separate components separately

Chaitin's Reduction:

- Remove any nodes of degree < 2 from the graph
- Iterate until all nodes are of degree >= 2
- If a better lower bound on X(G) is known, use that instead of 2

### Heuristic Greedy Sequential Coloring

Basic idea:

- Let P be a permutation of the vertices of V
- For each v in P, color v with the smallest legal color

Can fix P up front, or determine next element dynamically

Heuristic fails by using too many colors

- Performance Guarantee: X(H(G)) / X(G)
- Performance Guarantee is usually linear

### Fixed Permutations

Random (RS): Fast, but works poorly

Largest-degree First (LF): Fast, works better

Smallest Last (SL):

- Order vertices from smallest to largest "reduced degree"
- P is reverse of this sequence
- Fast, works still better
- Colors all planar graphs in 6 colors!

### Dynamic Permutations

Connected Sequential (CS): Ensure that every vertex in P is connected to a predecessor in P

- Static method
- Fast (e.g. DFS, BFS)
- Avoids some pathologies, e.g. Cn

Saturation Largest First (SLF): Color vertices in order of most neighbor colors, break ties by largest degree

- O((|V| + |E|) lg |V|) time (how?)
- Works well

Greedy Inductively Sequential (GIS): Color vertices by exhausting each color in turn

`To exhaust color c: while there is a set W of vertices that can be colored with c Let v be a vertex in W with smallest degree in the subgraph of uncolored vertices color v with c`

- O(|V||E|) time
- Good performance guarantee: O(n / lg n)
- Not so great in practice

### Color Interchange

If a vertex v requires a new color during greedy sequential coloring:

`for each color c1 neighboring v for each color c2 not neighboring v swap c1 and c2 in G if the result is still a legal coloring stop undo the swap fail`

If interchange succeeds, then v can be colored with an existing color

### Improving Performance By Search

Sometimes worth paying lots of extra computation cost to reduce X(H)

Obvious method: Optimizing Search

- Find X(H) by applying some heuristic H
- Set a bound k = X(H) - 1
- Run H again, but instead of assigning color k + 1, fail and backtrack
- Must allow H to choose any color, not just lowest priority
- But try in priority order

- Repeat until fail or out of time

Gets expensive fast

### Complexity Results

General Graphs

- 2-coloring: O(|E|) time
- 3+-coloring: NP-complete

Planar Graphs

- 2-coloring: O(|E|) time
- 3-coloring: NP-complete
- 4+-coloring: O(1) time (yes)

### Direct Search

```
To find a coloring of a partially-colored graph G
a heuristic H and a color bound k
if G is totally colored
return (G, k)
let v be the next vertex in V according to H
if no color in 1..k is a legal color for v
color v with k + 1
return partial-color(G, k + 1)
k_min <- |V|
for c = 1 .. k
if c is not a legal color for v
continue
color v with c
(G', k') <- partial-color(G, k)
if k' < k_min
G_min <- G'
k_min <- k'
return (G_min, k_min)
```

### SAT-based Search

Basic idea

- Build a prop SAT instance that is satisfiable iff graph G can be colored with k colors
- Run a stock SAT solver on G
- Binary search or something for best coloring
- Translate the result out

Works because modern SAT solvers are magic fast

Easier than building a custom search

### SAT Transformation For Graph Coloring

```
SAT-from-GC(graph G=(V, E), limit k colors):
-- enforce the edge constraints
∀ (v[i], v[j]) in E
∀ c in 1..k
emit clause (¬ v[i,c] ∨ ¬ v[j,c])
-- ensure that every vertex is colored
∀ i in 1..|V|
emit clause (v[i,1] ∨ v[i,2] ∨ .. ∨ v[i, k])
-- ensure that every vertex is uniquely colored
∀ i in 1..|V|
∀ c in 1..k
∀ c′ in 1..k
if c ≠ c′
emit clause (¬ v[i,c] ∨ ¬ v[i,c′])
```