Suppose instead of coloring the vertices of a graph we color the edges. If we color the edges so that edges with a common end vertex have different colors and we use as few colors as possible we get a proper edge coloring. The number of colors used in a proper edge coloring of a graph is called the chromatic index of the graph. We use the notation Χ'(G) for the chromatic index of the graph G.
When you use the Petersen program to find the chromatic index of a graph you might want to first make the edges thicker so that the colors are easy to see. You do this by selecting Picture | Edges | Line width in the main Petersen frame.
- If a graph contains a vertex of degree n what is the smallest chromatic index it can have?
- Use the Petersen program to find the chromatic index of each of the five platonic graphs. (In the program select Properties | Chromatic index).
- Use the program to find the chromatic index of the Petersen graph.
- If a graph G1 is a subgraph of G2 what can you say about X'(G1) and X'(G2) ?
- Use the program to find the chromatic index of the complete graphs K3, K4, K5, K6, K7, K8, K9, K10. (K9 takes quite a while.)
- What do you think the chromatic index of Kn is?
Java Web Start Activity:
We shall start by studying the chromatic numbers of complete graphs with an even number of vertices. We start with some examples. They will give you ideas on how to write a general proof in the next question. The Java Web Start application below shows you how to properly color the edges of K4 using 3 colors, K6 using 5 colors, K8 using 7 colors, ... K14 using using 13 colors.
- Prove that the edges of the graph K2n can be colored using 2n-1 colors.
- We know that we can properly color the edges of K2n using 2n-1 colors. Prove that the chromatic index of the graph K2n is 2n-1.[Hint: What is the degree of each of the vertices of K2n?]
We now turn our attention to the complete graphs with an odd number of vertices. The next question is very easy if you did the previous ones.
- Prove that the edges of the graph K2n-1 can be properly colored using 2n-1 colors. We shall prove that this is actually the chromatic index but we need to first study the Pidgeonhole Principle.
is as follows: If m pidgeons occupy
n pidgeonholes and m > n then at least one
pidgeonhole contains two or more pidgeons.
You probably don't spend your time watching pidgeons so think of it like this: If you have m students living in a dorm with n rooms and if m > n then at least one room has two or more residents.
Now suppose you have ninety students and only twenty dorm rooms. Then one can see that at least one room will have five or more students because four in each room would only account for eighty students. We are not going to talk only about pidgeons or students. In general if you have m items and you assign each item to one of n categories and m > n there will be at least two items of the same category.
- Prove the following version of the pidgeonhole principle. If m pidgeons occupy n pidgeonholes and m > n then at least one pidgeonhole contains ⌈m/n⌉ or more pidgeons where ⌈x⌉ is the smallest integer larger than or equal to x, also known as the ceiling function . [Hint: Try a proof by contradiction].
We shall now prove that the chromatic index of K5 is 5.
You will prove the general case for K2n-1 in the next question.
We have already shown that the edges of K2n-1 can be properly colored using 2n - 1 colors so we have that the edges of K5 can be properly colored using 5 colors. We also know that the vertices of K5 have degree 4 so we cannot color the edges properly with less than 4 colors. We therefore only have to show that the edges of K5 can not be properly colored using 4 colors.
Suppose to the contrary that we can color the (1/2)*5*4 = 10 edges of K5 properly using four colors. If you think of the edges as the items and the colors as the categories then by the pidgeonhole principle there is at least one color that is used on ⌈10/4⌉ = 3 or more edges. Take three edges of the same color. They have six endpoints. Again, using the pidgeonhole principle it means, since K5 has only five vertices, that there is a vertex that is the endpoint of at least two edges of the same color. (Here the "items" are the six endpoints and the "categories" are the five vertices of K5).This contradicts the assumption that it is a proper edge coloring and so we can't color K5 using four colors. Therefore the chromatic index of K5 is 5.
- Prove that the chromatic index of K2n-1 is 2n - 1.
© C. Mawata