Graph Coloring

Graph Coloring Pratishtha Pandey 3rd C.S.E

1

Coloring Graphs This handout: • Coloring maps and graphs • Chromatic number • Problem Definition • Our Algorithms • Applications of graph coloring 2

Coloring Graphs  Definition:

A graph has been colored if a color has been assigned to each vertex in such a way that adjacent vertices have different colors.

 Definition:

The chromatic number of a graph is the smallest number of colors with which it can be colored. In the example above, the chromatic number is 4. 3

Preliminaries A Graph With 6 Vertices and 8 Edges

A Vertex

An Edge 4

Preliminaries Adjacent vertices

5

Preliminaries Adjacent vertices

A

6

Preliminaries Adjacent vertices B

B and C are adjacent to A A

C

7

The Graph Coloring Problem



Objective: Assign colors to vertices so that adjacent vertices do not have the same color and use as few colors as possible

8

The Graph Coloring Problem A Valid Coloring



Objective: Assign colors to vertices so that adjacent vertices do not have the same color and use as few colors as possible

9

The Graph Coloring Problem An Invalid Coloring



Conflict

Objective: Assign colors to vertices so that adjacent vertices do not have the same color and use as few colors as possible

10

The m-Coloring optimization Problem 

Objective: Minimize the number of colors used

Total Colors Used: 5

Total Colors Used: 3 11

Coloring Graphs Naïvely 



Question: Can an n-vertex graph be colored with k colors? (This question is equivalent to the graph coloring problem.) Naïve algorithm: try all possible ways of assigning k colors to the n vertices 

 

If a valid coloring is found then answer yes. Otherwise, answer no Time: there are kn possible colorings to check Example: Can a 30-vertex graph be colored with 3 colors?  330 possible colorings  

106 colorings per second 6 MILLION YEARS !!! 12

Graph Coloring  As 



A

an example:

The vertices are enumerated in order A-F The colors are given in order: R, G, B

B

F

C

E D

13

Graph Coloring A B

F

C

E D

14

Graph Coloring A B

F

C

E D

15

Graph Coloring A B

F

C

E D

16

Graph Coloring A B

F

C

E D

17

Graph Coloring A B

F

C

E D

18

Graph Coloring A B

F

C

E D

19

Graph Coloring A B

F

C

E D

20

Graph Coloring A B

F

C

E D

21

Graph Coloring A B

F

C

E D

22

Graph Coloring A B

F

C

E D

23

A

Graph Coloring

B

F

C

E D

24

Complexity of Graph Coloring  Complexity:

Algorithm for finding the optimal solution requires exponential time.



Run Time: O(2nn).



Heuristics: Find good solutions in a reasonable amount of time

25

Coloring Planar Graphs  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 1850s. Finally proved in 1976 (Appel and Haken) by the aid of computers. 26

Coloring maps 

Color a map such that two regions with a common border are assigned different colors.



Each map can be represented by a graph:  



Each region of the map is represented by a vertex; Edges connect two vertices if the regions represented by these vertices have a common border.

The resulting graph is called the dual graph of the map. 27

28

Graph Theory for the Four Color Conjecture

29

Graph Theory for the Four Color Conjecture

30

Graph Theory for the Four Color Conjecture

31

Any Planar Map Is Four-Colorable Planar graph - a graph drawn in a plane without any of its edges crossing or intersecting Each vertex (A,B,C,D,E) represents a region in a graph Each edge represents regions that share a boundary

“In any plane graph each vertex can be assigned exactly one of four colors so that adjacent vertices have different colors.” -Four-Color Conjecture 32

An Application of Graph Coloring Class Scheduling Chem

Cannot be offered at the same time

Math

Art

Bio

Music

• Math – Bio • Math – Chem • Bio – Music • Bio – Econ • Music – Chem • Music – Econ • Chem – Art • Art – Econ

Econ 33

An Application of Graph Coloring Class Scheduling Chem

Cannot be offered at the same time

Math

Art

Bio

Music

• Math – Bio • Math – Chem • Bio – Music • Bio – Econ • Music – Chem • Music – Econ • Chem – Art • Art – Econ

Econ 34

An Application of Graph Coloring Class Scheduling Chem

Cannot be offered at the same time

Math

Art

Bio

Music

• Math – Bio • Math – Chem • Bio – Music • Bio – Econ • Music – Chem • Music – Econ • Chem – Art • Art – Econ

Econ 35

An Application of Graph Coloring Class Scheduling Chem

Cannot be offered at the same time

Math

Art

Bio

Music

• Math – Bio • Math – Chem • Bio – Music • Bio – Econ • Music – Chem • Music – Econ • Chem – Art • Art – Econ

Econ 36

An Application of Graph Coloring Class Scheduling Chem Math

Art

Bio

Music

Goal : minimize the number of periods (colors) used Econ 37

An Application of Graph Coloring Class Scheduling Chem Math

Schedule Art

Bio

• Period 1 • Period 2

Music

• Period 3

Econ 38

Optimization Problems 



The previous examples simply found all the solutions (Nqueens) or any single solution (Graph Coloring) What if we have a cost associated with each solution and we want to find the optimal solution 



As an example take Weighed Graph Coloring  R  $2, G  $3, B  $5, Y  $2  A fully connected graph of 3 vertices Note that some of the connections on the next slide are missing to keep the picture fairly clean 39

Weighted Graph Coloring By state space tree

40

m-Coloring of a Graph  We

represent graph by adjacency matrix G[1:n,1:n),Where G[i,j]=1 if (i,j) is an edge of G. Otherwise, G[i,j]=0 The colors are represented by 1,2….,m. and solutions are given by the n-tuple(x1, …,xn),where xi is the color of node i. Array x[]=0 firstly; 41

Algorithm mColoring(k) // This algorithm was formed using the recursive backtracking

schema.The graph is represented by its boolean adjacency matrix G[1:n,1:n]. // All asignment of 1,2,….,m to the vertices are assigned distinct integers are printed. k is the index of the next vertex to color. { Repeat { NextValue(k); //Assign to x[k] a legal color. if (x[k]=0) then return; // No new color possible if(k=n) then // At most color have been used to color write (x[1:n]);

else mColoring(k+1); } until (false); } 42

Algorithm NextValue(k) { repeat { x[k]:=(x[k]+1) mod(m+1); //Next highest colour. 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 colors. if ((G[k,j]=!0) and (x[k]=x[j])) // If (k,j) is and edge and if adj. vertices have same color. then break; } if (j=n+1) then return; } until (false); //otherwise find another color. } 43

Time Bounded The upper bound on the computing time of mColoring can be derived at by noticing that the number of internal nodes nin the state space tree is

∑i=0 mi .

At each1internal node, O(mn) time is spent by NextValue to determine the children corresponding to legal colorings. Hence the total time is bounded by i+1 i n+1 nn ∑ m n= ∑ m n = n(m -2)/(m-1) i=0 i=1 1

=O(nmn)

44

4-Node Graph 1

4

2

3

45

X1 =

1

3 2

2

X 2=

1

X 3=

X 4=

2

3

3

1

3

2

2

3

1

2

3 1

3

1

3

2

3 1

1

3

2

1

2

3 1

2

3

1

2

1

2

3

1

2

46

Other Applications of Graph Coloring CPU Registers

Classroom/Final Schedules

Football games

Radio Network

47

Summary Many problems that appear different on the surface can be efficiently reduced to each other, revealing a deeper similarity

48

Thank You

49