Graph Coloring

Graph Coloring: 

In Graph Theory, graph coloring is a special case of graph labeling. It is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In the easiest form it is a way of coloring the vertices of a graph so that no two adjacent vertices share the same color, this is called vertex coloring. An edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. 

A proper vertex coloring of the Petersen graph with three colors

The convention of using colors originates from coloring the countries of a map, where each face is literally covered. By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. For example: In mathematical and computer representations, it is typical to use the first few positive or nonnegative integers as the colors. In general we can use any finite set as the "color set." Graph coloring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a color is assigned, or even on the color itself. It has even reached popularity with the public in the form of the popular number game Sudoku. 

There are twelve different ways to color the map from above using three colors. 

A coloring using at most k colors is called k-coloring. The smallest number of colors needed to color a graph G is called its chromatic number, and is often denoted X(G) or Y(G). The chromatic number of a graph G is the smallest number of colors needed to color the vertices of G so that no two adjacent vertices share the same color. 

Examples: 

Examine Questions: Find the chromatic number for each graph listed below?  

Citations: Wikipedia, and Google images