Graph Theory Lessons

Lesson 8: Graph Coloring

Get the graph of a cube (it is under the Platonic Graph menu item). Click Properties and Chromatic number. What this does is to color the vertices of the graph using as few colors as possible and making sure that adjacent vertices always have different colors. We shall call such a coloring a proper coloring. The cube, for example, can be properly colored using just two colors.

Fig. 11, A properly colored cube.

The number of colors used is called the chromatic number of the graph. We use X(G) to denote the chromatic number of the graph G.

In the applet below draw a few graphs on the left side. The applet will display a proper coloring of the graph you draw.

Use the program to find the chromatic number of each of the five platonic graphs.
Use the program to find the chromatic number of the complete graphs K₅, K₇, K₁₀.
From part 2, what do you think the chromatic number of K_n is?
Use the program to find the chromatic number of the Petersen graph.
If a graph G₁ is a subgraph of G₂ what can you say about X(G₁) and X(G₂)?
If a graph contains a triangle (a subgraph isomorphic to K₃) what is the smallest chromatic number it can have?
What is the only graph with n vertices and chromatic number 1?
Graph coloring can be used to solve problems involving scheduling and assignments. Here are some examples:
Suppose you want to schedule final exams and, being very considerate, you want to avoid having a student do more than one exam a day. We shall call the courses 1,2,3,4,5,6,7. In the table below a star in entry ij means that course i and j have at least one student in common so you can't have them on the same day. What is the least number of days you need to schedule all the exams? Show how you would schedule the exams.

.	1	2	3	4	5	6	7
1	.	*	*	*	-	*	*
2	*	.	*	-	-	-	*
3	*	*	.	*	-	-	-
4	*	-	*	.	*	*	-
5	-	-	-	*	.	*	-
6	*	-	-	*	*	.	*
7	*	*	-	-	-	*	.

Suppose you run a day care for an office building and there are seven children A,B,C,D,E,F,G. You need to assign a locker where each child's parent can put the child's food. The children come and leave so they are not all there at the same time. You have 1 hour time slots starting 7:00 a.m. to 12:00 noon. A star in the table means a child is present at that time. What is the minimum number of lockers necessary? Show how you would assign the lockers.

.	A	B	C	D	E	F	G
7:00	*	-	-	*	*	-	-
8:00	*	*	*	-	-	-	-
9:00	*	-	*	*	-	*	-
10:00	*	-	*	-	-	*	*
11:00	*	-	-	-	-	*	*
12:00	*	-	-	-	*	-	-

Answers

e-mail: C. Mawata