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
- The chromatic number is denoted by ฯ(G) for a graph G.
- A complete graph with n vertices has a chromatic number of n.
- A bipartite graph has a chromatic number of 2.
- Determining the chromatic number is an NP-hard problem.
- 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?
"Chromatic number" appears in:
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.
