# Total coloring of a fuzzy graph.

1. IntroductionThe concept of total coloring as a combination of vertex and edge coloring of a graph G has already been studied by M. Rosenfeld [4]. Total coloring refers to coloring the vertices and edges of G in such a way that no two adjacent vertices, no two adjacent edges (edges which are incident on a common vertex) and no edge and its end vertices are assigned the same color.

Two types of coloring namely vertex coloring and edge coloring are usually associated with any graph. A third natural coloring called the total coloring was introduced by M. Behzad and Vizing [5]. They conjectured that [[chi].sub.T] (G) [less than or equal to] [delta] (G) + 2, where [[chi].sub.T] (G) denotes total chromatic number and [delta] (G) denotes the maximum degree of G.

Vertex coloring: Vertex coloring of a graph [1] refers to assigning colors to vertices so that adjacent vertices are differently colored. Let N denote the set of all natural numbers and assume that a distinct and unique natural number is associated with each color. Given a graph G = (V, E), a vertex coloring function is a function CV: V [right arrow] N such that [C.sub.V] (u) [not equal to] [C.sub.V] (v) for any two adjacent vertices u and v. A vertex k-coloring [C.sup.k.sub.V] is a vertex coloring function in which no more than k different colors are used. In other words [C.sup.k.sub.v] : V [right arrow] {1, 2,.......k}.

A graph is said to be vertex k - colored if it admits a vertex k - coloring. The minimum value of k for which G is vertex k - colored is called vertex chromatic number of G and is denoted by [[chi].sub.V] (G).

Edge coloring: Edge coloring of a graph [1] refers to assigning colors to edges so that adjacent edges are differently colored. It is known that every graph G can be edge colored with at most [delta] (G) + 1 colors and at least [delta] (G) colors are always necessary.

Given a graph G = (V, E), an edge coloring function is a function [C.sub.E]: E [right arrow] N such that [C.sub.E] (i, j) [not equal to] [C.sub.E] (i, k) and [C.sub.E] (i, j) [not equal to] [C.sub.E] (l, j) for all edges (i, j), (i, k) and (l, j) [member of] E. An edge k - coloring [C.sup.k.sub.E] is an edge coloring function in which no more than k different colors are used. In other words, [C.sup.k.sub.E]: E [right arrow] {1, 2 ,..........k}.

A graph is said to be edge k-colored if it admits an edge k-coloring. The minimum value of k for which G is edge k-colored is called edge chromatic number of G and is denoted by [[chi].sub.E] (G).

Total coloring: A total coloring of a graph G is a coloring of the vertices and edges of G in such a way that no two adjacent elements have the same color. Adjacent elements here refer either to two vertices connected by an edge or to two edges incident on a common vertex or to an edge and its end vertices.

Given a graph G = (V, E), a total coloring function is a function [C.sub.T]: V [union] E [right arrow] N which satisfies the following conditions.

a. [C.sub.T] (u) [not equal to] [C.sub.T] (v) for any two adjacent vertices u, v [member of] V.

b. [C.sub.T] (i, j) [not equal to] [C.sub.T] (i, k) and [C.sub.T] (i, j) [not equal to] [C.sub.T] (l, j) for all edges (i, j), (i, k) and (l, j) [member of] E.

c. [C.sub.T] (u) [not equal to] [C.sub.T] (u, v) [C.sub.T] (v) [not equal to] [C.sub.T] (u, v) for any two adjacent vertices u, v [member of] V.

A total k coloring [C.sup.k.sub.T] is a total coloring function in which no more than k different colors are used. In other words [C.sup.k.sub.T] : V [union] E [right arrow] {1, 2...k}. A graph is said to be total k - colored if it admits a total k - coloring. The minimum value of k for which G is total k - colored is referred to as the total chromatic number of G and is denoted by [[chi].sub.T] (G).

The (d, f) - extended Total coloring function:

Definition: Consider a fuzzy graph G = (V, [rho], S, d, f) where V denotes the vertex set and p is a (partial) function defined on V x V. Note, that p (u, v) is defined only for those u, v [member of] V for which (u, v) [member of] E. p can take its values from [0, 1] or from a fuzzy set, S denotes the available color set, d denotes the dissimilarity measure and f denotes the scale function.

A (d, f) extended vertex coloring of G, denoted by [C.sub.Vdf] or simply [C.sub.V] is a mapping [C.sub.V]: V [right arrow] S which satisfies the condition d ([C.sub.V](i), [C.sub.V](j)) [greater than or equal to] f([[rho].sub.i,j]) for all i, j [member of] V for which (i, j) [member of] E.

A (d, f) extended vertex k-coloring [C.sup.k.sub.Vdf] or simply [C.sup.k.sub.V], is a (d, f) extended vertex coloring function which takes maximum k different colors. In other words, [C.sup.k.sub.V] : V [right arrow] S where S = {1, 2,....k} satisfying the following.

d ([C.sup.k.sub.V] (i), [C.sup.k.sub.V] (j)) [greater than or equal to] f ([[rho].sub.i,j]) for all i, j [member of] V for which (i, j) [member of] E.

A (d, f) extended edge coloring of G, denoted by [C.sub.Edf] or simply [C.sub.E] is a mapping [C.sub.E]: E [right arrow] S which satisfies the condition

d (C (i, j), C (i, l)) [greater than or equal to] [conjunction] {f([[rho].sub.i,j]), f([[rho].sub.i,l])} for all edges (i, j) and (i, l) .

d (C (i, j), C (l, j)) [greater than or equal to] [conjunction] {f([[rho].sub.i,j]), f([[rho].sub.l,j]) for all edges (i j) and (l, j) .

A (d, f) extended edge k - coloring [C.sub.Edf] [C.sup.k.sub.Edf] or simply [C.sup.k.sub.E] is a (d, f) extended edge coloring function which takes maximum k different colors. In other words, [C.sup.k.sub.E] : E [right arrow] S where S = {1, 2,.....k} which satisfies the following

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

A (d, f) extended total coloring of G denoted by [C.sub.Tdf] or simply [C.sub.T] is a mapping from V [union] E to S satisfying the following.

d([C.sub.T](i), [C.sub.T](j)) [greater than or equal to] f([[rho].sub.i,j]) for all i, j [member of] V. (2)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

A (d, f) extended total k-coloring [C.sub.kTdf] or simply [C.sup.k.sub.T], is a (d, f) extended total k coloring function which takes maximum k different colors. In other words, [C.sup.k.sub.T]: V [union] E [right arrow] S where S = {1, 2,.......k} satisfying the conditions (2), (3) and (4) given above.

Following examples illustrate that total coloring of a fuzzy graph differs from total coloring of a crisp graph.

Example: Let G = (V, p, S, d, f) be a fuzzy graph where V = {A, B, C, D} and I = Image (p) = {n, l, m, h} where n, l, m and h stand for null, low, medium and high respectively. We assume that n < 1 < m < h. p is defined by the following matrix.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let S = {1, 2, 3, 4} be the color set and d be the dissimilarity measure defined as d (r, s) = [absolute value of r - s]

Let the scale function f be defined as follows

Table 1: Scale function. I n 1 m h f(I) 0 1 2 3

This fuzzy graph is shown in the figure given below.

[FIGURE 1 OMITTED]

It is possible to vertex color the above fuzzy graph with the following assignment of colors.

a. [C.sup.4.sub.T] (A) = 1, [C.sup.4.sub.T] (B) = 2 or 3, [C.sup.4.sub.T] (C) = 1, [C.sup.k.sub.T] (D) = 4.

b. [C.sup.4.sub.T] (A) = 4, [C.sup.4.sub.T] (B) = 2 or 3, [C.sup.4.sub.T] (C) = 4, [C.sup.4.sub.T] (D) = 1.

The assignment of colors in case (a) satisfies the equation (2) as shown below

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But with this assignment of colors to vertices, it is not possible to color the edges.

Note that the edge AD can be colored with either 2 or 3 only, edge BD can be colored with either 1 or 3 when B is colored with 2 and D is colored with 4 or edge BD can be colored with either 1 or 2 when B is colored with 3 and D is colored with 4, edge CD can be colored with either 2 or 3 only.

Case 1: [C.sup.4.sub.T] (AD) = 2, [C.sup.4.sub.T] (BD) = 1. This assignment of colors is possible because d ([C.sup.4.sub.T] (AD), [C.sup.4.sub.T] (BD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1. But now it is not possible to color CD with 2 or 3. The former is ruled out because AD is already colored with 2 and the latter is not possible because in that case d([C.sup.4.sub.T](AD), [C.sup.4.sub.T](CD)) = 1 whereas f ([[rho].sub.A,D]) [conjunction] f([[rho].sub.C,D]) is 2 which violates equation (3).

Case 2: [C.sup.4.sub.T](AD) = 2, [C.sup.4.sub.T](BD) = 3. This assignment of colors is possible because d ([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1. However it is now not possible to color CD with either 2 or 3 because these colors are already assigned to edges AD and BD.

Case 3: [C.sup.4.sub.T](AD) = 3. Then [C.sup.4.sub.T](BD) cannot be 3 and the only possibility is that [C.sup.4.sub.T](BD) = 1. This assignment of colors is possible because d([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 2 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.C,D]) = 1. Now it is not possible to color CCD with 43(which is already assigned to AD) and also with 2 because in this case d([C.sup.4.sub.T](AD), [C.sup.4.sub.T](CD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.C,D]) = 2 which violates equation (3).

Case 4: [C.sup.4.sub.T](AD) = 3, [C.sup.4.sub.T](BD) = 2. This assignment of colors is possible because d ([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1. However it is now not possible to color CD with either 2 or 3 because these colors are already assigned to edges AD and BD.

The assignment of colors in case (b) satisfies the equation (2) as shown below

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

But with this assignment of colors to vertices, it is not possible to color the edges.

Note that the edge AD can be colored with either 2 or 3 only, edge BD can be colored with either 3 or 4 when B is colored with 2 and D is colored with 1 or edge BD can be colored with either 2 or 4 when B is colored with 3 and D is colored with 1, edge CD can be colored with either 2 or 3 only.

Case 1: [C.sup.4.sub.T](AD) = [C.sup.4.sub.T](BD) = 3.This assignment of colors is possible because d ([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1.However it is now not possible to color CD with either 2 or 3 because these colors are already assigned to edges AD and BD.

Case 2: [C.sup.4.sub.T](AD) = 2, [C.sup.4.sub.T](BD) = 4. This assignment of colors is possible because d ([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 2 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1. But now it is not possible to color CD with 2 or 3. The former is ruled out because AD is already colored with 2 and the latter is not possible because in that case d([C.sup.4.sub.T](AD), [C.sup.4.sub.T](CD)) = 1 whereas f ([[rho].sub.A,D]) [conjunction] f([[rho].sub.C,D]) is 2 which violates equation (3).

Case 3: [C.sup.4.sub.T](AD) = 3, [C.sup.4.sub.T](BD) = 4. This assignment of colors is possible because d ([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1. Now it is not possible to color CD with 3 (which is already assigned to AD) and also with 2 because in this case d([C.sup.4.sub.T](AD), [C.sup.4.sub.T](CD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.C,D]) = 2 which violates equation (3).

Case 4: [C.sup.4.sub.T](AD) = 3, [C.sup.4.sub.T](BD) = 2. This assignment of colors is possible because d ([C.sup.4.sub.T](AD), [C.sup.4.sub.T](BD)) = 1 whereas f([[rho].sub.A,D]) [conjunction] f([[rho].sub.B,D]) = 1. However it is now not possible to color CD with either 2 or 3 because these colors are already assigned to edges AD and BD.

Thus it is not possible to color the above graph with the available colors.

In a (d, f)--extended total k coloring, it might happen that there are some colors which are not assigned to any of the vertices or edges, as shown in the following example.

Example: Let G = (V, [rho], S, d, f) be a fuzzy graph where V = {A, B, C, D, E}, I = Image ([rho]) = {n, l, m, h} where n, l, m and h have the same definitions as in the above example.

[rho] is defined by the following matrix.

Let S = {1, 2, 3, 4, 5, 6} be the color set and d be the dissimilarity measure given below:

Table 2 : The dissimilarity measure table. 1 2 3 4 5 6 1 0 3 3 4 2 5 2 3 0 4 4 2 3 3 3 4 0 6 1 5 4 4 4 6 0 2 5 5 2 2 1 2 0 3 6 5 3 5 5 3 0

Let the scale function f be defined as follows:

Table 3: Scale function. I n l m h f(I) 0 2 3 4

This fuzzy graph is shown in the figure below and p is defined by the following matrix.

[FIGURE 2 OMITTED]

A (d, f) - extended total coloring is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that color 5 is not assigned to any of the vertices or edges of G.

3. To determine the (d, f) total chromatic number

We read the graph in the form of an adjacency matrix adjMatrix [][]. The membership grades on the edges of the graph are stored in a two dimensional array weight [][]. The number of colors k available to color the graph and their color difference table (color Table[][]) are also read. Class node with 'index' and 'deg' as member variables is created. class edge with a, b and color as member variables is created. The vertices are sorted in descending order and stored in vertex array vertex [ ]. An array of edges e [totaldeg] is created and array e [enumber] results after removing the redundant edges.

The program first vertex color the graph by calling procedure greedycol (v, 0, C[] , vMax, cMax) where

v = 0, the first node to be colored, C[] array to store the color assigned to nodes, vMax, the first node with highest assigned color and cMax, the highest assigned color.

To edge color the graph, program calls the procedure grapgColor (adjMatrix, n, k) to properly color the graph. This procedure in turn calls the procedure edgeColor (e, eNumber, 0), to start coloring the edges of the graph. The importance of this procedure is that, it is recursively called to color all the edges of the graph. For each edge, it get list of colors from procedure getavailcol (), after removing all the colors already used to color the edges incident on the vertex, colors used to color the vertex considered and by removing those colors which does not satisfy the color difference table. Color the edge with the first available color (preferred color). If not possible to color the edge considered, it backtracks to change the color of the already colored previous edge with next preferred color and continue to color the edges. The procedure edgecolor() returns true to grapgcolor () only when all edges are colored. Colors used to color the edges are now stored in the final colorset [] array. The procedure grapgcolor () uses this final colorset [] to check whether it is possible to color the edges of the graph (proper coloring) using colors of this final colorset.

sub greedycol (v 0, C[], vMax , cMax) // Vertex coloring istop = 0, i = v 0, c = C[i] // ith node, c color do while (istop = 0) j = 0 // previous node do while (j < i) if (d[c][C[j] < weight [i][j]]) // c and C[j] are not compatible c = c + 1 // consider next color if (c [greater than or equal to] cMax) // indicating not possible to color i th node j = i else j = 0 else // c and C[j] are compatible j = j + 1 // Another previous node endif enddo if (c < cMax) // c is compatible C[i] = c, i = i + 1, c = 0 // color i th node with c, start coloring next node if (i > n) then istop = 1 // all nodes are colored else // c is not compatible i = i - 1 c = C [i] + 1 // backtrack to change already colored ith node color endif enddo endsub sub grapgColor (adjMatrix, n, k) // To Properly edge color the graph node vertex // array of vertices sorted in 'Descending' order of their degree edge e // array of eNumber of edges with 'a' , 'b' and 'color' as elements if (edgeColor (e, eNumber, 0)) // start coloring edges of the graph get finalColorSet array // array of colors with finalK numbers of colors for(i = 0 to eNumber) for(j = 0 to finalK) if (finalColorSet [j] = = getAvailColor (e, i, n, 0, finalColorSet[j])) e[i].color = finalColorSet [j] // assign new color toe [i] and update colMatrix endif get finalColorSet array return true // returns to main with finalColorSet indicating successful coloring end if return false // returns to main indicating coloring not possible end sub sub edgeColor ( edge e, eNumber, index) // To color all edges of the graph get number of available colors availcolor for (ic = 1 up to (ic [less than or equal to] availColor and !colored (e,eNumber) and index < eNumber)) for (i = index to i < eNumber ) e[i].color = -1 colMatrix[e[i].a][e[i].b] = k + 1 colMatrix[e[i].b][e[i].a] = k + 1 end for // Undo wrong choice c = getAvailcolor (e, index, n, ic, k + 1) if ( c = = -1) break e [index] .color = c // color e[index] with color c and update colMatrix edgeColor (e, eNumber, index + 1) // call recursively edgeColor end for if (all edges in e colored) return true // returns to grapgColor else return false // back track to edgeColor to change previous edge color end sub sub main Read the graph of n vertices in terms of Adjacency matrix adjMatrix [i][j] Read the membership values for the edges of the graph weight [i][j] Read the number of available colors k and color difference table colorTable [i][j] Initialize cMax = k + 1 and C [0] = -1. Initiate Colmatrix. if (edge exists between i and j) colMatrix [i][j]= k + 1 else colMatrix [i][j] = -1 greedycol (0,C,vMax,cMax) // Vertex coloring if(grapgColor (adjMatrix, n, k)) // calling grapgColor print finalColorSet and K // K final total number of colors used to color the graph else print "can't be colored ..." end sub

Example 1:

[FIGURE 3 OMITTED]

Consider a graph with 6 vertices whose adjacency matrix is given below:

Table 4: The adjacency matrix table. A B C D E F A 0 1 0 0 0 1 B 1 0 1 0 1 0 C 0 1 0 1 0 1 D 0 0 1 0 1 0 E 0 1 0 1 0 1 F 1 0 1 0 1 0

The membership grades on the edges are given by the following table:

Table 5: The membership grades table. A B C D E F A 0 3 0 0 0 5 B 3 0 5 0 3 0 C 0 5 0 1 0 5 D 0 0 1 0 3 0 E 0 3 0 3 0 3 F 5 0 5 0 3 0

The number of available color is 4 and their color difference table is given by the following table.

Table 6: The color difference table. 1 2 3 4 1 0 2 3 3 2 2 0 2 3 3 3 2 0 3 4 3 3 3 0

Then Output for vertex coloring is as follows:

The vertex A is colored with 2, The vertex B is colored with 4, The vertex C is colored with 2,

The vertex D is colored with 1, The vertex E is colored with 2, The vertex F is colored with 4

But it is not possible to color edges with these four colors.

But if the number of available color is 5, then it is possible to color the graph with the following color difference table:

Table 7: The color difference table. 1 2 3 4 5 1 0 3 4 4 5 2 3 0 4 5 3 3 4 4 0 3 5 4 4 5 3 0 4 5 5 3 5 4 0

Outputs:

The vertex A is colored with 1, the vertex B is colored with 5, the vertex C is colored with 1,

The vertex D is colored with 2, the vertex E is colored with 1, the vertex F is colored with 5.

The edge (B, A) is colored with 3, the edge (B, C) is colored with 2, the edge (B, E) is colored with 4,

the edge (C, D) is colored with 3, the edge (C, F) is colored with 4, the edge (E, D) is colored with 5,

The edge (E, F) is colored with 3, the edge (F, A) is colored with 2.

The (d, f) total chromatic number is 5 and the colors used are 1, 2, 3, 4 and 5.

Example 2: Consider the graph given in example 1 with color difference table given below.

Table 8: The color difference table. 1 2 3 4 5 1 0 4 5 3 4 2 4 0 3 5 4 3 5 3 0 3 4 4 3 5 3 0 3 5 4 4 4 3 0

Out put:

The vertex A is colored with 1, the vertex B is colored with 3, the vertex C is colored with 1,

the vertex D is colored with 2, the vertex E is colored with 1, The vertex F is colored with 3

The edge (B, A) is colored with 5, the edge (B, C) is colored with 2, the edge (B, E) is colored with 4,

The edge (C, D) is colored with 5, the edge (C, F) is colored with 4, the edge (E, D) is colored with 3,

The edge (E, F) is colored with 5, the edge (F, A) is colored with 2

The (d, f) total chromatic number is 5 and the colors used are 1, 2, 3, 4 and 5.

4. Conclusion

We note that the (d, f) Total chromatic number heavily depends on the d function and f function. We are now studying the relationship between (d, f) total chromatic number, d function and f function. We are also attempting to develop Total coloring of a fuzzy graph, chromatic number etc without considering the d and f functions.

References

[1] Nora Hartsfield, Gerhard Ringel, PEARLS in GRAPHTHEORY, A comprehensive Introduction, Academic press, Inc.

[2] Susana Munoz, M. Teresa Ortuno, Javier Ramirez, Javier Yanez, Coloring fuzzy graphs, Omega 33 (2005) 211-221

[3] Dr.V.Ramaswamy and Mrs.Poornima B, Edgecoloring of a Fuzzy Graph, Advances in Fuzzy Mathematics volume 4, No 1 (2009) P 49-58.

[4] M. Rosenfeld, On the total coloring of certain graphs, Israel J. Math, 396-402, 1971.

[5] M. Behzad, Graphs and their chromatic numbers, Ph.D. Thesis, Michigan State University, 1965.

B. Poornima, Department of Computer Science and Engineering, BIE T, Davangere, Karnataka, India. E-mail: poornimajeju@rediffmail.com.

V. Ramaswamy, Department of Information Science and Engineering, BIE T, Davangere, Karnataka, India. E-mail: researchwork04@yahoo.com.

Printer friendly Cite/link Email Feedback | |

Author: | Poornima, B.; Ramaswamy, V. |
---|---|

Publication: | International Journal of Computational and Applied Mathematics |

Date: | Jan 1, 2010 |

Words: | 4379 |

Previous Article: | Cayley's theorem for centre of Pre [A.sup.*]-algebras. |

Next Article: | Inductive proofs on the determinants of generalized Vandermonde matrices. |