image
Graph Theory Lessons

rule

previous index next Lesson 14: Graph Vertex Coloring


Petersen Activity:
Get the graph of a cube (it is under the Graph | Named Graph | Platonic Graph | Cube | Non Planar menu item). Click Properties | 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 vertex coloring. The cube, for example, can be properly colored using just two colors. Figure 14.1 shows a properly colored cube

A properly colored cube
Fig 14.1. A proper vertex coloring of the cube

We usually abbreviate "proper vertex coloring" and just say "proper coloring". The number of colors used in a proper coloring of a graph is called the chromatic number of the graph. We use the notation Χ(G) for the chromatic number of the graph G .

Java Web Start Activity:
In the Java Web Start Application 14.1 below, draw a few graphs on the pane. The application will display a proper coloring of the graph you draw.

Java Web Start Application 14.1: Graph coloring

Questions:
  1. Use the Petersen program to find the chromatic number of each of the five platonic graphs. (Select Properties | Chromatic number).
  2. Use the program to find the chromatic number of the complete graphs K4, K5, ... K10.
  3. From part 2, what do you think the chromatic number of Kn is? Prove your conjecture. [Hint: Try a proof by induction].
  4. Use the program to find the chromatic number of the Petersen graph.
  5. If a graph G1 is a subgraph of G2 what can you say about X(G1) and X(G2) ?
  6. If a graph contains a triangle (a subgraph isomorphic to K3) what is the smallest chromatic number it can have?
  7. 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:

Questions:
  1. 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 i,j 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 * * - - - * .
  1. 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 * - - - * - -

Java Web Start Activity:
In the programming exercise you will be asked to find a proper coloring of a graph. Study the way that the Java Web Start application below works to get ideas on how you will implement your algorithm.

Java Web Start Application 14.2: Finding a proper coloring of a graph

Programming Task

Answers


© C. Mawata