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