A new color change to improve the coloring of a graph

AbstractFor some special classes of graphs an optimal coloring can be obtained by the “Kempe method”: color as many vertices as possible with q given colors, and then make one of these colors available for an uncolored vertex x0 by interchanging the two colors of a “bicolor component”. It is well known that in general these interchanges cannot lead to an optimal coloring.We shall define here another type of color changes which can always lead to an optimal coloring. The basic tool is the concept of an “odd alternating sequence”