Chromatic number

Definition

The chromatic number of a graph is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color. It is a fundamental concept in graph coloring problems.

5 Must Know Facts For Your Next Test

1. The chromatic number is denoted by χ(G) for a graph G.
2. A complete graph with n vertices has a chromatic number of n.
3. A bipartite graph has a chromatic number of 2.
4. Determining the chromatic number is an NP-hard problem.
5. The Four Color Theorem states that any planar graph can be colored with no more than four colors.

Review Questions

• What does the chromatic number represent in graph theory?
• How many colors are needed to color a bipartite graph?
• Why is determining the chromatic number considered an NP-hard problem?

Related terms

Graph Coloring: Assigning colors to the vertices of a graph so that no two adjacent vertices share the same color.

Planar Graph: A graph that can be drawn on a plane without any edges crossing.

NP-Hard Problem: A class of problems for which no polynomial-time solution algorithm is known.