1 of 24

Graph Theory

Chapter 8 Graph Coloring

​

大葉大學 資訊工程系 黃鈴玲

2010.12

2 of 24

Contents

  • 8.1 The Chromatic Number of a Graph
  • 8.2 Multipartite Graphs
  • 8.3 Results for General Graphs
  • 8.4 Planar Graphs
  • 8.5 Edge Coloring of a Graph

2

3 of 24

8.1 The Chromatic Number of a Graph

3

Definition 8.1

點著色：相連的點塗上不同的顏色

4 of 24

4

Example 8.2

5 of 24

5

Definition 8.4

存在3-coloring ⇒ χ(G) ≤ 3

有子圖是K3 ⇒ 不存在2-coloring ⇒ χ(G) ≥ 3

⇒ χ(G) = 3

(著色數)

6 of 24

Homework

Ex8.2 Determine the chromatic number of the � Petersen graph.

6

7 of 24

7

Observation 8.7

Theorem 8.9

(by induction on k)

8 of 24

8.2 Multipartite Graphs

8

Example 8.10

9 of 24

9

Homework

10 of 24

10

11 of 24

11

Corollary 8.11

Definition 8.12

12 of 24

8.3 Results for General Graphs

12

Theorem 8.19

13 of 24

13

G

u1

u2

u5

u3

u6

u4

1

2

1

2

3

3

Example

N1={} (編號比自己小的鄰居)

N2={u1}

N3={}

N4={u1}

N5={u2, u3, u4}

N6={u2, u3, u4}

S1=(1) (鄰居未使用的最小顏色)

S2=(1, 2)

Δ=3, 用4色

S3=(1, 2, 1)

S4=(1, 2, 1, 2)

S5=(1, 2, 1, 2, 3)

S6=(1, 2, 1, 2, 3, 3)

14 of 24

14

G

u1

u4

u6

u5

u3

u8

u7

Homework

Ex: For the following graph G, find the colorings given by Delta Plus One Coloring Algorithm. What is the chromatic number χ(G) of G?

u2

節點編號會影響顏色數

15 of 24

15

Example 8.21

Theorem 8.22

Definition 8.24

16 of 24

16

Theorem 25

17 of 24

17

G

u5

u3

u4

u6

u2

u1

2

1

1

1

2

2

依照degree由大到小為節點編號

N1={} (編號比自己小的鄰居)

N2={u1}

N3={u2}

N4={u1, u3}

N5={u1, u3}

N6={u2, u4}

S1=(1) (鄰居未使用的最小顏色)

S2=(1, 2)

S3=(1, 2, 1)

S4=(1, 2, 1, 2)

S5=(1, 2, 1, 2, 2)

S6=(1, 2, 1, 2, 2, 1)

只需2色!!

χ(G) ≤ max(min{1, 4}, min{2, 4},� min{3, 4}, min{4, 4}, � min{5, 3}, min{6, 3})=4

18 of 24

18

G

u5

u3

u4

u6

u2

u1

3

3

1

1

3

2

依照degree由大到小為節點編號

N1={} (編號比自己小的鄰居)

N2={u1}

N3={u1, u2}

N4={u1, u2}

N5={u1, u2}

N6={u3, u4}

S1=(1) (鄰居未使用的最小顏色)

S2=(1, 2)

S3=(1, 2, 3)

S4=(1, 2, 3, 3)

S5=(1, 2, 3, 3, 3)

S6=(1, 2, 3, 3, 3, 1)

只需3色

χ(G) ≤ max(min{1, 5}, min{2, 5},� min{3, 4}, min{4, 4}, � min{5, 3}, min{6, 3})=4

19 of 24

19

G

u1

u5

u4

u8

u7

u6

u3

u2

Homework

Ex: For the following graph G, find the colorings given by Delta Plus One Coloring Algorithm and Greedy Coloring Algorithm. What is the chromatic number χ(G) of G?

20 of 24

20

8.4 Planar Graphs

Theorem 8.29 (Four Color)

For a planar graph G, we have χ(G) ≤ 4.

21 of 24

8.5 Edge Coloring of Graphs

21

Definition 8.35

(幫edge著色，共用端點的edge必須使用不同顏色)

Definition 8.37

22 of 24

22

Observation 8.40

K4

u4

u3

u2

u1

3

1

2

2

3

1

K4

u5

u4

u2

u1

u3

Ex: 請給出一個� 5-edge coloring

23 of 24

23

Theorem 8.41

K3,3

u3

u4

u2

u1

v3

v1

v2

v4

Corollary 8.42

24 of 24

24

Theorem 8.43