About This Graph Coloring

This figure represents a total coloring of this bipartite graph. A total coloring is one in which each edge and each vertex is assigned a color, such that no co-incident edges receive the same color, no adjacent vertices receive the same color, and no vertex receives the same color as an incident edge. See the chapter by Amanda Chetwynd Total Colourings of Graphs in the book Graph Colourings edited by Roy Nelson and Robin J. Wilson(cite key che90 in the bibliography ). The coloring of this graph is not optimal since it is possible to achieve a total coloring with fewer colors.

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