Graph colorings

Definition

Graph coloring is the assignment of labels, called colors, to elements of a graph subject to certain constraints. Typically, no two adjacent vertices share the same color.

5 Must Know Facts For Your Next Test

1. The minimum number of colors needed to color a graph without adjacent vertices sharing the same color is called its chromatic number.
2. A bipartite graph can always be colored with just two colors.
3. Planar graphs can be colored with at most four colors according to the Four Color Theorem.
4. An edge coloring assigns colors to edges so that no two edges sharing a vertex have the same color.
5. Graph coloring can be used to solve problems like scheduling and assigning frequencies in mobile networks.

Review Questions

• What is the chromatic number of a bipartite graph?
• What theorem states that any planar graph can be colored with at most four colors?
• How does edge coloring differ from vertex coloring?

Related terms

Chromatic Number: The minimum number of colors needed to color a graph such that no two adjacent vertices share the same color

Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent

Four Color Theorem: A theorem stating that any planar graph can be colored using no more than four distinct colors