Printer Friendly

Total coloring of a fuzzy graph.

1. Introduction

The 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.
COPYRIGHT 2010 Research India Publications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2010 Gale, Cengage Learning. All rights reserved.

Article Details
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.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters