Complete Colorings
Gary Chartrand, Ping Zhang · 2008
The proper vertex colorings of a graph G in which we are most interested are those that use the smallest number of colors. These are, of course, the χ(G)-colorings of G. If χ(G) = k, then every k-coloring of G (using the colors 1, 2, . . . , k as usual) has the property that for every two distinct colors i and j with 1 ≤ i, j ≤ k, there are adjacent vertices of G colored i and j. If this were not the case, then the set of vertices colored i and the set of vertices colored j could be merged into a single color class, resulting in a (k − 1)-coloring of G, which is impossible. In fact, the chromatic number of a graph G can be defined as the smallest positive integer k for which there is a k-coloring of G having the property that for every two distinct colors, there are adjacent vertices in G assigned these colors. In this chapter, we are primarily interested in vertex colorings of graphs having this property and in concepts related to this property.