Graph Coloring

 Graph Coloring is an assignment of colors (or any
distinct marks) to the vertices of a graph. Strictly

speaking, a coloring is a proper coloring if no two
adjacent vertices have the same color.
f : V (G )  S
 Definition: A graph is planar if it can be drawn in a plane
without edge-crossings.
 The four color theorem: For every planar graph, the

chromatic number is ≤ 4.
 Was posed as a conjecture in the 1850’s. Finally proved in
1976(Appel and Haken) by the aid of computers.
 A vertex coloring is an assignment of labels or colors
to each vertex of a graph such that no edge connects
two identically colored vertices
 Similar to vertex coloring, except edges are color.
 Adjacent edges have different colors.
 K-Coloring
◦ A k-coloring of a graph G is a mapping of V(G) onto
the integers 1..k such that adjacent vertices map into
different integers.
◦ A k-coloring partitions V(G) into k disjoint subsets
such that vertices from different subsets have
different colors.
 K-colorable
◦ A graph G is k-colorable if it has a k-coloring.
 Chromatic Number
◦ The smallest integer k for which G is k-colorable is
called the chromatic number of G, is denoted by the
χ(G).
 Many problems can be formulated as a graph coloring
problem including Time Tabling, Scheduling, Register
Allocation, Channel Assignment.
 A lot of research has been done in this area so much is
already known about the problem space.
 One way to approach map coloring is to
represent each region of the map with a
vertex of a graph.
 Two vertices are connected with an edge if
the regions they represent have a common
border.
 Coloring the map is then the same process as
coloring the vertices of a graph so that
adjacent vertices have different colors.
 Color the following map using four of fewer
colors:
A
D
C E
B
(G) = minimum number of colors needed for graph G
 A Graph is k-chromatic if χ(G) = k
 Optimal coloring – proper k-coloring of a k-chromatic graph

◦ Vertex-coloring problems
 Is a graph k-colorable for given k?
 What is χ(G) / what is the optimal coloring?
Proper 6-coloring Optimal 4-coloring
Sequential Coloring Algorithm
Mark all entries in the palettes of all the nodes as available
Repeat:
1. Pick an uncolored node v
2. Let c be an available color (from v ‘s palette)
(such a color always exists)
3. Color node v with color c
4. Mark c as unavailable in the color
palette of every neighbor of v
Until all nodes are colored
15
Example execution
Palette of v 1
1 2 3
All are available colors

v1
16
Palette of v 1
1 2 3
Picks first available color

v1
1
17
Palette of v 2
1 2 3 4 5
v1
1
18
Palette of v 2
1 2 3 4 5

v1
1 v2
2
19
Palette of v 3
1 2 3 4

v1
1 v2
2
v3
20
Palette of v 3
1 2 3 4

v1
1 v2
2
v3 3
21
Termination
1 3
2 1 3 2
1 1
1 2 1
3 1 2
1 2
2 3
3
2 3
1
3 2 1
22
Graph Coloring state space
The backtracking search tree starts at non-labeled root.
• The immediate children of the root represent the available choices regarding the
coloring of the first vertex (vertex in this case) of the graph. However, the nodes of
the tree are generated only if necessary. The first(leftmost) child of the root
represents the first choice regarding the coloring of vertex a, which is to color the
vertex with color – this is indicated by the label assigned to that node. So far this
partial coloring does not violate the constraint that adjacent vertice be assigned
different colors.
• So we grow the tree one more level where we try to assign a color to the second
vertex (verter b) of the graph.
The leftmost node would represent the coloring of vertex b with color 1.
• However, such partial coloring where a=1 and b=1is invalid since the vertices a and
b are adjacent
• Also, there is no point of growing the tree further from this node since, no matter
what colors we assign to he remaining vertices, we will not get a valid coloring for all
of the vertices.
• So we prune (abandon) this path and consider an alternative path near where we
are.
• We try the next choice for the coloring of vertex b, which is to color it with color 2.
• The coloring a=1 and b=2 is a valid partial coloring so we continue to the next level
of the search tree
Algorithm mColoring(k)
// the graph is represented by its Boolean adjacency matrix G[1:n,1:n] .All
assignments //of 1,2,……….,m to the vertices of the graph such that adjacent
vertices are assigned //distinct integers are printed. ’k’ is the index of the next
vertex to color.
{ repeat
{ // generate all legal assignment for X[k].
Nextvalue(k); // Assign to X[k] a legal color.
if (X[k]=0) then return; // No new color possible.
if (k=n) then// Almost ‘m’ colors have been used to color the ‘n’ vertices
Write(x[1:n]);
else mcoloring(k+1);
}until(false);
}
Algorithm Nextvalue(k)
//*X[1],……X[k-1] have been assigned integer values in the range[1,m] such that adjacent values
have distinct integers.
A value for X[k] is determined in the range[0,m].X[k] is assigned the next highest numbers color
while maintaining distinctness form the adjacent vertices of vertex K. If no such color exists, then
X[k] is 0. */
{ repeat
{
X[k] = (X[k]+1)mod(m+1); // next highest color.
If(X[k]=0) then return; //All colors have been used.
for j=1 to n do
{ // Check if this color is distinct from adjacent color.
If((G[k,j]!= 0)and(X[k] = X[j]))
// If (k,j) is an edge and if adjacent vertices have the same color. then break;
}
if(j=n+1) then return; //new color found.
} until(false); //otherwise try to find another color.
}
Complexity:
The time spent by Nextvalue to

determine the children is (mn)
Total time is = (mn n).
M colors and N vertices

Graph Coloring

Uploaded by

Copyright:

Available Formats

Graph Coloring

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Graph Coloring

Uploaded by

Copyright:

Available Formats

 Graph Coloring is an assignment of colors (or any

distinct marks) to the vertices of a graph. Strictly

 The four color theorem: For every planar graph, the

 Optimal coloring – proper k-coloring of a k-chromatic graph

Until all nodes are colored

All are available colors

Picks first available color

Picks first available color

Picks first available color

Picks first available color

The time spent by Nextvalue to

You might also like