Graph Theory Lessons

Answers to Lesson 8

The table lists the chromatic numbers of the five platonic graphs.

Graph	Chromatic number
Tetrahedron	4
Cube	2
Octahedron	3
Icosahedron	4
Dodecahedron	3

The chromatic numbersof the complete graphs K₅, K₇, K₁₀ are 5, 7, and 10 respectively.
The chromatic number of the complete graph K_n is n.
The chromatic numberof the Petersen graph is 3.
If a graph G₁ is a subgraph of G₂ then
If a graph contains a triangle (a subgraph isomorphicto K₃) then the smallest chromatic number it can have is 3.
If a graph has with n verticesand chromatic number 1, then it has no edges (otherwise the chromatic number would be at least 2) so it must be the null graph N_n.
We need to first think about how we will model the problem as a coloring problem. We have courses 1, 2, ...,7, and a table in which 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. We will make a graph in which the vertices represent courses and two courses are adjacent if and only if they have at least one student in common. If we color that graph, then two courses which are adjacent will have different colors. We need to color that graph with the fewest possible colors.
Next we use the program to draw such a graph and color it. We get the following picture:

The chromatic number is 4 and a possible schedule is

Day Exam

1 1, 5

2 2, 4

3 3, 6

4 7

Note that this is not the only four coloring possible -- can you find other solutions?

We make a table for seven vertices A, B, C, D, E, F, G (one for each child) and a star in entry i,j means that there is a time when both child i and child j are at school and so they should not have the same locker.

	A	B	C	D	E	F	G
A	.	*	*	*	*	*	*
B	*	.	*	.	.	.	.
C	*	*	.	*	.	*	*
D	*	.	*	.	*	*	.
E	*	.	.	*	.	.	.
F	*	.	*	.	.	.	*
G	*	.	*	.	.	*	.

We get the following graph (vertex 1 represents child A, vertex 2 represents child B etc)

We can use four lockers. Child C and child E (vertices 3 and 5) share a locker (blue color) since they are never at school at the same time, and another locker is shared by the children B, D, G. Child A and child F each get a locker to themselves.

e-mail:C. Mawata

	A	B	C	D	E	F	G
A	.	*	*	*	*	*	*
B	*	.	*	.	.	.	.
C	*	*	.	*	.	*	*
D	*	.	*	.	*	*	.
E	*	.	.	*	.	.	.
F	*	.	*	.	.	.	*
G	*	.	*	.	.	*	.

Day	Exam
1	1, 5
2	2, 4
3	3, 6
4	7

	A	B	C	D	E	F	G
A	.	*	*	*	*	*	*
B	*	.	*	.	.	.	.
C	*	*	.	*	.	*	*
D	*	.	*	.	*	*	.
E	*	.	.	*	.	.	.
F	*	.	*	.	.	.	*
G	*	.	*	.	.	*	.

	A	B	C	D	E	F	G
A	.	*	*	*	*	*	*
B	*	.	*	.	.	.	.
C	*	*	.	*	.	*	*
D	*	.	*	.	*	*	.
E	*	.	.	*	.	.	.
F	*	.	*	.	.	.	*
G	*	.	*	.	.	*	.