Graph - Ch 4

8/3/2019 Graph - Ch 4

1/52

Chapter 4:

Vertex Colouring

8/3/2019 Graph - Ch 4

2/52

8/3/2019 Graph - Ch 4

3/52

4 Colour Problem (Pg 95 96)

Given a map with divided regions, how many

colours do we need so that:

Adjacent regions do not share the same colour?

8/3/2019 Graph - Ch 4

4/52


Proven that we need at most 4 colours.

Transform this problem into a Graph problem.

1

12

2

3

3

8/3/2019 Graph - Ch 4

5/52

Let each region be denoted by a vertex.

Two vertices are adjacent to each other if they

share common boundary (next to each other).


8/3/2019 Graph - Ch 4

6/52

The problem is reduced to colouring the

vertices such that no adjacent vertices share

the same colour.


8/3/2019 Graph - Ch 4

7/52

Colouring (Pg 96 99)

Extend this problem to general graphs.

A

k-colouring of graph G is a way to colour thevertices ofG such that

(i)At most kcolours are used.

(ii)Vertices that are adjacent are coloured using

different colours.

**kis a positive integer**

8/3/2019 Graph - Ch 4

8/52

Colouring (Pg 96 99)

IfG has a 3-colouring, then it has a 4-

colouring. (why?)

In general, ifG has a m-colouring, then it has

an n-colouring where both m, n are positive

integers and m < n.

Note there might be more than one possible

k-colouring for a graph.

8/3/2019 Graph - Ch 4

9/52

Examples (Pg 98-99)

Read Example 4.2.1

Question 4.2.1: A 4 Colouring ofG.

G

1 2

3

4

1

2

2

8/3/2019 Graph - Ch 4

10/52

Examples (Pg 98-99)


G

1 2

3

1

1

2

2

8/3/2019 Graph - Ch 4

11/52

Examples (Pg 98-99)


G

1 2

1

1

2

1

1

8/3/2019 Graph - Ch 4

12/52

Examples (Pg 98-99)

G has no 1-colouring because there exists twovertices which are adjacent.

What type of graph contains a 1-colouring?

8/3/2019 Graph - Ch 4

13/52

Examples (Pg 98-99)

Question 4.2.2: A 5-colouring ofG

1

2

3

4

5

1

2

3

4

8/3/2019 Graph - Ch 4

14/52

Examples (Pg 98-99)


1

2

3

4

1

1

2

3

4

8/3/2019 Graph - Ch 4

15/52

Examples (Pg 98-99)


1

2

2

3

1

1

2

3

2

8/3/2019 Graph - Ch 4

16/52

Examples (Pg 98-99)

No 2-colouring ofG because there is a C3.

Why?

Read Example 4.2.2.

8/3/2019 Graph - Ch 4

17/52

Chromatic Number (Pg 100)

Other than knowing a k-colouring of a graph

G, we are also interested in finding out the

minimum colours needed to colour a graph.

The chromatic number, , is the minimum

value ofksuch that G admits a k-colouring.

( )GG

8/3/2019 Graph - Ch 4

18/52


Question 4.2.3:

(a) 1 (e) 2

(b) 2 (f) 3

(c) 2 (g) 4

(d) 2 (h) 4

8/3/2019 Graph - Ch 4

19/52


Question 4.2.4: Largest value for is n.

When will a graph have ?

Ans:When G is a complete graph.

( )GG

( )G nG !

8/3/2019 Graph - Ch 4

20/52


Question 4.2.5:

Proof: Let . Since H is a subgraph ofG, His k-colourable. By the definition of ,

( ) ( )H GG Ge

( )G kG ! ( )HG

( ) ( )H k GG Ge !

8/3/2019 Graph - Ch 4

21/52

Chromatic number of special

graphs ( pg 102)Result 1: Let G be a graph of order n.

if and only ifG is Nn (null graph)( ) 1GG !

Proof (): Suppose G is not Nn (null graph), then

there exists two vertices which are adjacent.

Therefore .( ) 2GG u

8/3/2019 Graph - Ch 4

22/52


graphs ( pg 102)Result 2: Let G be a graph of order n.

if and only ifG is Kn.( )G nG !

Proof (): Suppose G is not Kn , then there exists two

vertices which are not adjacent. Then we can

colour the two vertices with same colour.

Hence .( ) 1G nG e

8/3/2019 Graph - Ch 4

23/52


graphs ( pg 102)Result 2: Example: let G be K4.

( ) 4GG ! ( ) 3 4 1HG ! e

8/3/2019 Graph - Ch 4

24/52

Let graph G be a cycle of order n, then

Chromatic number of bipartite

graphs ( pg 102-103)

2, even

( ) 3, odd

n

G nG

!

8/3/2019 Graph - Ch 4

25/52

Let graph G be a graph. IfG contains an odd

cycle as subgraph, then .



( ) 3GG u

Result 3: Let G be a graph.

if and only ifG is non-empty bipartite.( ) 2GG !

8/3/2019 Graph - Ch 4

26/52

Proof (

8/3/2019 Graph - Ch 4

27/52

Proof (=>) : Suppose G is not bipartite, then G

contains an odd cycle as a subgraph. Hence. Therefore taking the contrapositive

of the statement (with the fact that G is non-

empty),

G is bipartite.



( ) 3GG u

( ) 2GG !

**Now we can use vertex colouring to test if a

graph is bipartite**

8/3/2019 Graph - Ch 4

28/52


graphs (pg 104-106)Result 5: Let G be a graph andp be any positiveinteger. IfG contains Kp as a subgraph then

( )G pG u

This result is useful in 2 ways:

(i) Get a lower bound for

(ii) We can determine ifG contains Kp as a

subgraph.

( )GG

8/3/2019 Graph - Ch 4

29/52

Example 4.3.6 (pg 105-106)

Read Examples 4.3.4, 4.3.5

Example 4.3.6:

( ) 3GG u

Since C3 is a

subgraph ofG,

8/3/2019 Graph - Ch 4

30/52

Example 4.3.6 (pg 105-106)

Pick any C3 to colour first, try to keep thenumber of colours to 3.

Vertex whas no choice but to use 4th colour.

8/3/2019 Graph - Ch 4

31/52

Example 4.3.6 (pg 105-106)

This is a 4-colouring ofG.

( ) 4GG !

8/3/2019 Graph - Ch 4

32/52

Greedy Colouring Algorithim

Colouring method trial & error method.

Algorithm to colour vertices in systematicmanner.

Attempt to approximate .( )GG

8/3/2019 Graph - Ch 4

33/52


Step 1: Label the vertices v1, v2, ..., vn.

Step 2: Assign v1 with colour 1.

Step 3: Following the ordering of the vertices,

assign each vertex with the minimum colournumber such that it does not share the same

colours as its neighbour.

8/3/2019 Graph - Ch 4

34/52

Example 4.4.1:

Step 1: Give the vertices a certain labelling.


8/3/2019 Graph - Ch 4

35/52

Step 2: Assign v1 colour 1.


1

8/3/2019 Graph - Ch 4

36/52

Step 3: Assign v2 colour 1 (since v2 and v1 arenot adjacent.)


1 1

8/3/2019 Graph - Ch 4

37/52

Assign v2 colour 2 (since v3 and v1 areadjacent.)


1 1

2

8/3/2019 Graph - Ch 4

38/52

Assign v4 colour 3


1 1

2

3

8/3/2019 Graph - Ch 4

39/52

Assign v5 colour 4


1 1

2

3

4

8/3/2019 Graph - Ch 4

40/52

According to this particular labelling, we can

conclude that


3 ( ) 4GGe e

Can ( ) 3?GG !

8/3/2019 Graph - Ch 4

41/52

Consider another set of labelling for the

vertices


8/3/2019 Graph - Ch 4

42/52

Following Greedy Algorithim, we assign the

colours to each vertex in the following way:


v1 1

v2 2

v3 3

v4 2

v5 3

8/3/2019 Graph - Ch 4

43/52

We can conclude that


( ) 3.GG !

Number of colours used by Greedy ColouringAlgorithm depends on how we label the

vertices.

Try Question 4.4.1: ( ) 3.GG !

8/3/2019 Graph - Ch 4

44/52

Brooks Theorem (pg 119)

Greedy Colouring Algorithm gives us an upper

bound for ( ).GG

Colour assigned to a vertex depends on its

neighbours.

Try our best to assign colours that were usedby other vertices.

8/3/2019 Graph - Ch 4

45/52


Worst scenario: A vertex, vhas neighbours

assigned with all the colours being used.

Assign a new colour to v. So the number of

colours used is d(v) + 1.

v: no choice have to

use a new colour.

8/3/2019 Graph - Ch 4

46/52


For each vertex v, the largest colour we

have to use is d(v) + 1.

For a graph G, we will need at most

max{ d(vi)+ 1 | vi V(G)} = ( ) 1G(

( ) ( ) 1G GG@ e (

8/3/2019 Graph - Ch 4

47/52

Applications : Example*

Pg 125: Aim: Find minimum no. of storage rooms

CHEMICAL INCOMPATIBLEWITH:

U V, Y

V U,W,Z

W V,X,Z

X W,Y

Y X,U

Z V,W

8/3/2019 Graph - Ch 4

48/52

Applications *

Determine the following:

What should vertices represent? Which vertices should be adjacent?

What does the colouring represent?

What do we want to find?

8/3/2019 Graph - Ch 4

49/52

Applications *

Determine the following:

What should vertices represent? Chemicals

Which vertices should be adjacent?Incompatible ones (why?)

What does the colouring represent?

Different rooms

What do we want to find?

Chromatic number of graph

8/3/2019 Graph - Ch 4

50/52

Applications: Example *

UV W

XY

Z

G

8/3/2019 Graph - Ch 4

51/52

Application: Example *

G has a C3: ( ) 3GG u

Brooks theorem: ( ) 3 ( ) 4G GG( ! e

Is Find a 3 colouring.( ) 3?GG !

Is Explain why a 3 colouring is

impossible.( ) 4?GG !

8/3/2019 Graph - Ch 4

52/52

Applications: Example *

UV W

XY

Z

G

1

2

3

12

2

( ) 3GG@ Minimum we need3rooms

Documents

Graph - Ch 4