Graph Coloring

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.

See also

Chromatic Number, Chromatic Polynomial, Edge Coloring, Four-Color Theorem, k-Coloring, Labeled Graph, Polyhedron Coloring, Vertex Coloring

Explore with Wolfram|Alpha


Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1994.Morgenstern, C. and Shapiro, H. "Heuristics for Rapidly 4-Coloring Large Planar Graphs." Algorithmica 6, 869-891, 1991.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 Coloring

Cite this as:

Weisstein, Eric W. "Graph Coloring." From MathWorld--A Wolfram Web Resource.

Subject classifications