Coloring
A proper coloring or coloring of a graph assigns colors usually denoted by 1, 2, 3, … etc., to the vertices of G, one color per vertex, so that the adjacent vertices are assigned different colors.
- PDF / 285,179 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 47 Downloads / 242 Views
Coloring
Coloring of a graph Proper coloring: A proper coloring or coloring of a graph G assigns colors usually denoted by 1, 2, 3, … etc., to the vertices of G; one color per vertex, so that the adjacent vertices are assigned different colors. For example, Fig. 8.1 shows proper coloring of a graph.
8.1 Properly Colored Graph A graph in which every vertex has been assigned a color according to a proper coloring is called a properly colored graph. Fig. 8.1 A properly colored graph
k-Colorable: A k-coloring of G is a coloring which consists of k different colors and in this case, the graph G is said to be k-colorable.
S. Saha Ray, Graph Theory with Algorithms and its Applications, DOI: 10.1007/978-81-322-0750-4_8, Springer India 2013
125
126
8 Coloring
8.2 Chromatic Number The minimum number n, for which there is an n-coloring of the graph G, is called chromatic number or chromatic index of the graph G. It is denoted by vðGÞ. If vðGÞ ¼ k, then the corresponding graph G is called k-chromatic. For example, the graph in Fig. 8.1 is 4-chromatic. Theorem 8.1 Let G be a non-empty graph. Then vðGÞ ¼ 2 , i.e.,. 2-chromatic if and only if G is bipartite. Proof Let G be a bipartite graph with bipartition V ¼ X [ Y. Now, we assign color 1 to all the vertices in X and assign color 2 to all the vertices in Y. Then it gives a 2-coloring for G and so, since G is nonempty, vðGÞ ¼ 2: Conversely, suppose that vðGÞ ¼ 2, i.e., the graph G is 2-chromatic. Then, G has a 2coloring. To show: The graph G is bipartite. Let X be the set of all vertices with color 1 and Y be the set of all vertices with color 2. Since, the graph G is properly colored, no two vertices in X are adjacent to each other. Similarly, no two vertices in Y are adjacent to each other. So, since G is nonempty, every edge of G has one end vertex in X and another end vertex in Y. Therefore, G is a bipartite graph with bipartition V ¼ X [ Y. h Theorem 8.2 Let G be a graph then vðGÞ 3 if and only if G has an odd cycle. Proof Let G be a non-empty graph with at least two vertices, then G is bipartite if and only if it has no odd cycle. Then from the previous Theorem 8.1, vðGÞ ¼ 2 if and only if G has no odd cycle. Now, if the graph G has an odd cycle then the chromatic number of G should be greater than 2; since the graph has at least two vertices the chromatic number of G cannot be less than 2 , i.e., vðGÞ 6¼ 1. Moreover, we would require at least three colors just for that odd cycle in G. So, vðGÞ 3 if and only if the graph G has an odd cycle. h Theorem 8.3 A graph with at least one edge is 2-chromatic if and only if it has no odd cycles. Proof It follows from Theorem 8.1, since we know that if G has a non-empty graph with at least two vertices, then G is bipartite if and only if G has no odd cycles. h Theorem 8.4 Every tree with two or more vertices is 2-chromatic. Proof Consider the vertex v be the root of the tree T as shown in Fig. 8.2.
8.2 Chromatic Number
127
Fig. 8.2 A Properly colored tree
Now color the root vertex v with 1 then color all the verti
Data Loading...
