# Graph Coloring

Bart Massey

• 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

• 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′])