Edge Coloring - Examples

Examples

A cycle graph may have its edges colored with two colors if the length of the cycle is even: simply alternate the two colors around the cycle. However, if the length is odd, three colors are needed.

A complete graph K_n with n vertices may have its edges colored with n − 1 colors when n is an even number; this is a special case of Baranyai's theorem. Soifer (2008) provides the following geometric construction of a coloring in this case: place n points at the vertices and center of a regular (n − 1)-sided polygon. For each color class, include one edge from the center to one of the polygon vertices, and all of the perpendicular edges connecting pairs of polygon vertices. However, when n is odd, n colors are needed: each color can only be used for (n − 1)/2 edges, a 1/n fraction of the total.

Several authors have studied edge colorings of the odd graphs, n-regular graphs in which the vertices represent teams of n − 1 players selected from a pool of 2n - 1 players, and in which the edges represent possible pairings of these teams (with one player left as "odd man out" to referee the game). The case that n = 3 gives the well-known Petersen graph. As Biggs (1972) explains the problem (for n = 6), the players wish to find a schedule for these pairings such that each team plays each of its six games on different days of the week, with Sundays off for all teams; that is, formalizing the problem mathematically, they wish to find a 6-edge-coloring of the 6-regular odd graph O₆. When n is 3, 4, or 8, an edge coloring of O_n requires n + 1 colors, but when it is 5, 6, or 7, only n colors are needed.