Abstract
In this chapter a particular type of graph labeling, called graph coloring, is introduced and discussed. In the first part, the simple type of coloring, vertex coloring, is focused. Thus, concerning vertex coloring, some terms and definitions are introduced. Next, some theorems and applying those theorems, some coloring algorithms and applications are introduced. At last, some helpful concepts such as critical graphs, list coloring, and vertex decomposition are presented and discussed. In the second section, edge coloring is focused. Thus, concerning edge coloring, some terms and definitions are described, some important information about edge chromatic number and edge list coloring is presented, and applying them, classification of graphs using the coloring approach is summarized. At last some helpful concepts such as edge list coloring and edge decomposition are illustrated and discussed.
TopVertex Coloring
Using coloring the vertices of a graph G can be classified. It illustrates that the vertices with the same color have a common property.
It should be noted that in this chapter the study of vertex coloring of graphs is generally limited to simple graphs. Therefore a graph which has any loop in is assumed that it is not colorable, because the endpoint of a loop is adjacent to itself.
Consider the graph G to be a undirected and loopless graph (simple graph), a k-vertex coloring (for simplifying we can say k-coloring) of the graph G is defined as an assignment of k colors,1, 2, …, k, to the vertices of the graph G. This means that, vertex coloring of G = (V, E)can be formulated by a mapping c: V → S, where S illustrates a set of k colors; so, a k-coloring can be defined as an assignment of k colors to vertices of the graph G. Regularly, the set of colors, S, is taken to be {1, 2, …, k}. Also, a k-coloring can be considered as a partition {V1, V2, …, Vk} of V, where Vi denotes the set of vertices which have been allotted the color i. Therefore the sets Vi denotes the color classes.
Figure 1. 4-colorable graph and (b) 3-chromatic graph
Where in the graph G no two adjacent vertices are allotted the same color we say the coloring is proper coloring. Just for loopless graphs a proper coloring is possible. A k-coloring is a proper one when every color class is a stable set. The graph G is k-colorable if it has a proper k-coloring. Obviously, for every graph which is k-colorable then it is necessarily l-colorable for any l ≥ k.