Restricted Vertex Colorings
Gary Chartrand, Ping Zhang · 2019
When attempting to properly color the vertices of a graph, there may be instances when there is only one choice for the color of each vertex of the graph, every vertex of the graph has some preassigned restriction on the choice of a color that can be used for the vertex, or some vertices of the graph have been given preassigned colors and the remaining vertices must be colored according to these restrictions. This chapter explores colorings with such restrictions. It discusses uniquely colorable graphs, including uniquely 2-colorable and uniquely 3-colorable graphs. An associated set of permissible colors for each vertex of a graph is commonly called a color list. When attempting to provide a proper coloring of a given graph, it might be reasonable to begin with a coloring of some of the vertices of the graph so that the colors assigned to two adjacent vertices are different.