Considering only the vertex coloring, we notice that four colors are used while only two are necessary since the graph is bipartite. On the other hand, if the simple sequential vertex coloring algorithm is applied to this graph, with the pairs of vertices of the same color being first in the input, then four colors will be used.

This is the second of an infinite sequence of graphs showing that
on
a graph of *2n* vertices the simple sequential algorithm may
require *n+1* colors. (The first graph in the sequence is a
path of length 3). For this and many other examples see David S.
Johnson's papers ** Worst Case Behavior of Graph Coloring
Algorithms** and **
Approximation Algorithms for Combinatorial Problems** (listed in
the
bibliography under cite keys joh74a and joh74b).

As an exercise the viewer may wish to determine whether any optimal total coloring of this graph is also an optimal vertex coloring.

Back to the coloring page.

August 27, 2010