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