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 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
             undo the swap
  • 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
        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′])
Last modified: Tuesday, 20 May 2014, 9:52 AM