A proper coloring of a graph is a graph coloring in which adjacent objects receive different colors. In a proper vertex coloring, adjacent vertices have different colors, while in a proper edge coloring, edges sharing a vertex have different colors. When the type of object being colored is not specified, "proper coloring" usually means a proper vertex coloring (Jensen and Toft 1994).
Proper Coloring
See also
Edge Coloring, Graph Coloring, k-Coloring, Vertex ColoringExplore with Wolfram|Alpha
References
Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1994.Cite this as:
Weisstein, Eric W. "Proper Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ProperColoring.html