Graph coloring is the assignment of labels or colors to the edges or vertices of a graph. The most common types of graph colorings are edge coloring and vertex coloring. A coloring in which adjacent objects receive different colors is called a proper coloring. The corresponding optimization problems are the edge coloring problem and vertex coloring problem.
Graph Coloring
See also
Additive Coloring, Choice Number, Chromatic Number, Chromatic Polynomial, Color Coding, Colorful Cycle, Coloring, Correspondence Coloring, Edge Coloring, Edge Coloring Problem, Four-Color Theorem, k-Coloring, Labeled Graph, List Coloring, Polyhedron Coloring, Proper Coloring, Proper Hat Guessing Number, Vertex-Colored Graph, Vertex Coloring, Vertex Coloring ProblemExplore with Wolfram|Alpha
References
Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1994.Morgenstern, C. A. and Shapiro, H. D. "Heuristics for Rapidly Four-Coloring Large Planar Graphs." Algorithmica 6, 869-891, 1991. https://doi.org/10.1007/BF01759077.Opsut, R. J. and Roberts, F. S. "On the Fleet Maintenance, Mobile Radio Frequency, Task Assignment, and Traffic Phasing Problems." In The Theory and Applications of Graphs (Ed. G. Chartrand, Y. Alavi, D. L. Goldsmith, L. Lesniak-Foster, and D. R. Lick). New York: Wiley, pp. 479-492, 1981.Skiena, S. "Graph Coloring." §5.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 210-216, 1990.Wagon, S. "An April Fool's Hoax." Mathematica in Educ. Res. 7, 46-52, 1998.Wagon, S. "Coloring Planar Maps and Graphs." Ch. 24 in Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 507-537, 1999.Referenced on Wolfram|Alpha
Graph ColoringCite this as:
Weisstein, Eric W. "Graph Coloring." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphColoring.html