Types of Graph Coloring

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 k-chromatic if its chromatic number is exactly 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/

Leave a Reply