Vertex coloring is the simplest form of labelling a graph. “When used without any qualification, a **coloring** of a graph is almost always a ‘*proper vertex coloring*,’ namely a labelling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color.”

Also, graph coloring with the most (k) colors is called ‘proper’ **k-coloring**. Coloring with the smallest number of colors that is needed is called **chromatic number** or sometimes represented as y(G). ” A graph that can be assigned a ‘proper’ *k*-coloring is ** k-colorable**, and it is

**if its chromatic number is exactly**

*k*-chromatic*k*.” Vertices are also classified in same color or color classes, independent sets are formed from such classes.

http://dictionary.sensagent.com/Graph%20coloring/en-en/

## 9 Replies to “Types of Graph Coloring”