Graph coloring is a systematic assignment of labels, traditionally called colors, to the elements of a graph, most commonly its vertices, so that no two adjacent elements share a color; edge coloring and face coloring apply the same idea to edges and to the faces of a planar graph. The convention of using colors comes from coloring the countries of a political map, generalized first to coloring the faces of a graph embedded in the plane and, through planar duality, to coloring vertices in general. Graph coloring has both practical applications and deep theoretical challenges, and remains a very active field of research. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Connections
Associated With
The four color theorem is a graph coloring result: it bounds at four the number of colors a planar map's regions need so no two adjacent regions share one.
Additional Source Graph Coloring (Wikipedia)Lead section
In Branch
Sources
1. Graph Coloring (Wikipedia)
Wikimedia FoundationLead section
graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph
History section
While trying to color a map of the counties of England in 1852, Francis Guthrie postulated the four color conjecture, noting that four colors were sufficient to color the map so that no regions sharing a common border received the same color.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.