# Introduction To Graph Coloring

2 min read

**Introduction**

- When a map is colored, two regions with a common border are customarily assigned different colors.
- We want to use a small amount of colors instead of just assigning every region its own color.
- Each map in a plane can be represented by a graph.

- Each region is represented by a vertex.
- Edges connect to vertices if the regions represented by these vertices have a common border.
- Two regions that touch at only one point are not considered adjacent.

- The resulting graph is called the dual graph of the map.
- A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.
- The chromatic number of a graph is the least number of colors needed for a coloring of the graph.
- The Four Color Theorem: The chromatic number of a planar graph is no greater than four.

**Example:** Chromatic number of the graph shown below

The chromatic number must be at least 3 since a, b, and c must be assigned different colors. So lets try 3 colors first.

3 colors work, so the chromatic number of this graph is 3.