Advanced
CHROMATIC NUMBER OF BIPOLAR FUZZY GRAPHS
CHROMATIC NUMBER OF BIPOLAR FUZZY GRAPHS
Journal of Applied Mathematics & Informatics. 2016. Jan, 34(1_2): 49-60
Copyright © 2016, Korean Society of Computational and Applied Mathematics
  • Received : February 24, 2015
  • Accepted : June 01, 2015
  • Published : January 30, 2016
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
About the Authors
A. TAHMASBPOUR
R. A. BORZOOEI

Abstract
In this paper, two different approaches to chromatic number of a bipolar fuzzy graph are introduced. The first approach is based on the α -cuts of a bipolar fuzzy graph and the second approach is based on the definition of Eslahchi and Onagh for chromatic number of a fuzzy graph. Finally, the bipolar fuzzy vertex chromatic number and the edge chromatic number of a complete bipolar fuzzy graph, characterized. AMS Mathematics Subject Classification : 05C99.
Keywords
1. Introduction
In 1965, Zadeh [20] first proposed the theory of fuzzy sets. In 1994, Zhang [21 , 22] initiated the concept of bipolar fuzzy sets as a generalization of fuzzy sets. Bipolar fuzzy sets are extension of fuzzy sets whose range of membership degree is [−1,1]. In a bipolar fuzzy sets, the membership degree 0 of an element means that the element is irrelevant to the corresponding property, the membership degree (0, 1] of a element indicates that the element somewhat satisfies the property, and the membership degree [−1, 0) of an element indicates that the element somewhat satisfies the implicit counter property. For example, sweetness of foods is a bipolar fuzzy set. If sweetness of foods has been given as positive membership values then bitterness foods is for negative membershipvalues. Other tastes like salty, sour, pungent are irrelevant to the corresponding property. So these foods are taken as zero membership values. Graph theory is rapidly moving into the mainstream of mathematics because of its applications in diverse fields which include biochemistry (DNA double helix and SNP assembly problem), Chemistry (model chemical compounds) electrical engineering (communications networks and coding theory), computer science (algorithms and computations) and operations research (scheduling). Graph coloring is one of the most important concepts in graph theory and is used in many real time applications like Job scheduling, Aircraft scheduling, computer network security, Map coloring and GSM mobile phone networks, Automatic channel allocation for small wireless local area networks. In 1975 Rosenfeld ]undefined [16] introduced the concept of fuzzy graphs. Akram [1] defined bipolar fuzzy graphs. Talebi and Rashmanlou investigated isomorphism on interval-valued fuzzy graphs [19] . Dey and Pal [4] introduced a coloring function based on α cut of fuzzy graph G . Swaminathan [17] introduced fuzzy chromatic sum, fuzzy chromantic join, find a natural application in scheduling theory. Poornima and Ramaswamy [11] considered total coloring of a fuzzy graph. Ananthanarayanan and Lavanya [2] defined fuzzy chromatic number, fuzzy total chromatic number using α cuts of the fuzzy graph which are crisp graphs. Firouzian and Nouri Jouybari [7] analyzed traffic lights problem by fuzzy chromatic number. The fuzzy vertex coloring of a fuzzy graph was defined by authors Eslahchi and Onagh [6] and another approach of vertex coloring of fuzzy graph was used in S. Munoz, T. Ortuno. Pal and Rashmanlou [10] studied irregular interval valued fuzzy graphs. Also, they defined antipodal interval valued fuzzy graphs [13] , balanced interval valued fuzzy graphs [14] , some properties of highly irregular interval valued fuzzy graphs [15] . In our paper, we determine bipolar fuzzy chromatic number of a bipolar fuzzy graph G whose edge and vertices both are bipolar fuzzy set.
2. Preliminaries
Two types of coloring namely vertex coloring and edge coloring are usually associated with any graph. A third natural coloring called the total coloring. This three types of coloring are defined as follows:
( i ) Vertex coloring of graph 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 N such that CV ( u ) ≠ CV ( v ) for any two adjacent vertices u and v . A vertex K -coloring
PPT Slide
Lager Image
is a vertex coloring function in which no more than K different colors are used. In other words
PPT Slide
Lager Image
: V → {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 denoted by XV ( G ).
( ii ) Edge coloring of a graph 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 δ ( G )+1 colors and at least δ ( G ) colors are always necessary. Given a graph G = ( V,E ), an edge coloring function is a function CE : E N such that CE ( i, j ) ≠ CE ( i, k ) and CE ( i, j ) ≠ CE ( l, j ) for all edges ( i, j ), ( i, k ) and ( l, j ) ∈ E . An edge K -coloring
PPT Slide
Lager Image
is an edge coloring function in which no more than K different colors are used. In other words,
PPT Slide
Lager Image
: E → {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 XE ( G ).
( iii ) 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 CT : V E N which satisfies the following conditions.
( i ) CT ( u ) ≠ CT ( v ), for any two adjacent vertices u, v V .
( ii ) CT ( i, j ) ≠ CT ( i, k ) and
CT ( i, j ) ≠ CT ( l, j ), for all edges ( i, j ), ( i, k ) and ( l, j ) ∈ E .
( iii ) CT ( u ) ≠ CT ( u, v )
CT ( v ) ≠ CT ( u, v ), for any two adjacent vertices u, v V .
A total K coloring
PPT Slide
Lager Image
is a total coloring function in which no more than K different colors are used. In other words
PPT Slide
Lager Image
: V E → {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 XT ( G ) (See [7] ).
The triple G = ( V,σ,m ) is called a fuzzy graph on V where σ and m are fuzzy sets on V and V × V , respectively, such that m ({ u, v }) ≤ min { σ ( u ), σ ( v )}, for all u, v V . Note that a fuzzy graph is a generalization of crisp graph in which m ( v ) = 1, for all v V and m ( i, j ) = 1 if ( i, j ) ∈ E , otherwise m ( i, j ) = 0 (See [2] ).
Definition 2.1 ( [1] ). Let X be a nonempty set. A bipolar fuzzy set B on X is an object having the form B = {( x,m + ( x ), m ( x )), x X }, where m + : X → [0, 1] and m : X → [−1, 0] are mapping. A bipolar fuzzy graph with an underlying set V is defined to be the pair G = ( A,B ) where
PPT Slide
Lager Image
is a bipolar fuzzy set on V and
PPT Slide
Lager Image
is a bipolar fuzzy set on E V × V such that
PPT Slide
Lager Image
Let G = ( A,B ) and G′ = ( A′,B′ ) be two bipolar fuzzy graphs. A homomorphism h : G G′ is a mapping h : V V′ which satisfies the following conditions:
PPT Slide
Lager Image
PPT Slide
Lager Image
Theorem 2.2 ( [3] ). Let G be a crisp graph and H be a subgraph of G. Then X ( H ) ≤ X ( G ).
3. Main results
Let G = ( A,B ) be a bipolar fuzzy graph, where
PPT Slide
Lager Image
be two bipolar fuzzy sets on a non-empty finite set V and E V × V , respectively. The positive and negative level set of fuzzy bipolar set A is defined as
PPT Slide
Lager Image
, for some u V },
PPT Slide
Lager Image
, for some u V } and the positive and negative level set of B is defined as
PPT Slide
Lager Image
for some ( u, v ) ∈ V × V },
PPT Slide
Lager Image
for some ( u, v ) ∈ V × V }. The fundamental set of the fuzzy bipolar graph G = ( A,B ) is defined as
PPT Slide
Lager Image
We define for α + L + , α L , G α+ = ( V α+ , E α+ ), where
PPT Slide
Lager Image
and G α = ( V α , E α ), where
PPT Slide
Lager Image
Definition 3.1. The chromatic number of G is defined as
PPT Slide
Lager Image
, maxX ( G α )), where X α+ and X α are the chromatic number of G α+ and G α , respectively and α + , α are the positive and negative different membership value of vertices and edges of graph G . Moreover, the chromatic number of bipolar fuzzy graph G = ( A,B ), is fuzzy number X ( G ) = {( X α+ , α + ), ( X α , α )}, where X α+ and X α are the chromatic number of G α+ and G α which α + L + ∪ {0} and α L . Two vertices u and v , for any strong edge in G , are called adjacent if
PPT Slide
Lager Image
. A family
PPT Slide
Lager Image
of bipolar fuzzy sets on set V , is called a ( k 1 , k 2 )-bipolar fuzzy coloring of G = ( A,B ), if
PPT Slide
Lager Image
PPT Slide
Lager Image
( iii ) for every strong edge ( x, y ) of G ,
PPT Slide
Lager Image
The minimum numbers k 1 and k 2 which there exists a ( k 1 , k 2 )-fuzzy bipolar coloring is called the bipolar fuzzy chromatic number of G and denoted by Xf ( G ) = ( Xf + ( G ), Xf ( G )).
Theorem 3.2. Let G = ( A,B ) and G′ = ( A′,B′ ) be two bipolar fuzzy graphs and h : G G′ be a homomorphism. Then for all α + L + and α L , X ( G α+ ) ≤ X ( G′ α + ) and X ( G α ) ≤ X ( G′ α ) and so X ( G ) ≤ X ( G′ ).
Proof . Let
PPT Slide
Lager Image
. We prove that h ( G α+ ) is a subgraph of G′ α + . Let
PPT Slide
Lager Image
Then there exist x, y G α+ such that x′′ = h ( x ) and y′′ = h ( y ). Since
PPT Slide
Lager Image
. Then
PPT Slide
Lager Image
. Now, let
PPT Slide
Lager Image
. Then there exist x, y E α+ such that x′′ = h ( x ) and y′′ = h ( y ). Since
PPT Slide
Lager Image
and so x′′y′′ E′ α+ . By Theorem 2.2, X ( h ( G α+ )) ≤ X ( G′ α + ). Since X ( h ( G α+ )) = X ( G α+ ), X ( G α+ ) ≤ X ( G′ α + ). Similarly, X ( G α ) ≤ X ( G′ α ). So by definition of chromatic number of bipolar fuzzy graph, X ( G ) ≤ X ( G′ ). □
Example 3.3. Let G = ( A,B ) be a fuzzy bipolar graph, where
PPT Slide
Lager Image
are two fuzzy bipolar sets on non-empty finite set V and E V × V . Moreover, let G has five vertices and membership value of those vertices that are A = {(0.9,−0.5), (0.7,−0.4), (0.8,−0.5), (0.7,−0.5), (1,−0.7)} and graph G has 10 edges. Consider the crisp graphs G α+ and G α corresponding to the values in the positive, negative level set of the bipolar fuzzy graph G given in Figure 1 . For every values of α + L + ∪{0} and α L , we find graphs G α+ and G α are showed in Figure 2 and Figure 3 and find its fuzzy bipolar chromatic number.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Graphs G α as followes:
In the above example, six crisp graphs G α+ = ( V α+ , E α+ ), five crisp graphs G α = ( V α , E α ) are obtained by considering the values for α + and α . Now it can be shown that the chromatic number of bipolar fuzzy graph G is XV ( G ) = {(5, 0.5), (3, 0.6), (3, 0.7), (2, 0.8), (1, 0.9), (1, 1), (1,−0.7), (1,−0.6), (3,−0.5), (3,−0.4), (4,−0.2), (5, 0)}.
PPT Slide
Lager Image
Example 3.4. Consider the bipolar fuzzy graph G = ( A,B ), where V = { v 1 , v 2 , v 3 , v 4 } and E = { v 1 v 2 , v 1 v 3 , v 1 v 4 , v 2 v 3 , v 3 v 4 }.
Consider the crisp graphs G α+ and G α corresponding to the values in the positive, negative level set of the bipolar fuzzy graph G given in Figure 4 , L + = {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.7} and L = {−0.4,−0.3,−0.2,−0.1}. For every values of α + L + , α L , we find graphs G α+ , G α and its edge coloring number and total coloring number. Graphs G 0.1 , G 0.2 , G 0.3 , G 0.4 , G 0.5 , G 0.7 are showed in Figure 5 , Graphs G 0 , G -0.4 , G -0.3 , G -0.2 , G -0.1 are showed in Figure 6 . In the above example, seven crisp graphs G α+ = ( V α+ , E α+ ), four crisp graphs G α = ( V α , E α ) are obtained by considering the values for α + , α . Now it can be shown that the edge, total chromatic number of bipolar fuzzy graph G is XE ( G ) = {(3, 0.1), (3, 0.2), (1, 0.3), (1, 0.4), (0, 0.5), (0, 0.7), (3, 0), (3,−0.1), (2,−0.2), (0,−0.3), (0,−0.4)}, XT ( G ) = {(5, 0.1), (3, 0.2), (3, 0.3), (3, 0.4), (1, 0.5), (1, 0.7), (5,−0.1), (4,−0.2), (1,−0.3), (1,−0.4), (5, 0)}.
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
Remark 3.1. For a bipolar fuzzy graph G = ( A,B ), if
PPT Slide
Lager Image
Theorem 3.5. For a bipolar fuzzy graph G = ( A,B ), X ( G ) = Xf ( G ).
Proof . Let G = ( A,B ) be a bipolar fuzzy graph on n vertices { v 1 , v 2 ,..., vn } and Xf ( G ) = ( k, k′ ). Then
PPT Slide
Lager Image
is a ( k, k′ )-bipolar fuzzy coloring. If C j+ and C j is the colors assigned to vertices in
PPT Slide
Lager Image
, where j + = 1, 2,..., k, j = 1, 2,..., k′ and
PPT Slide
Lager Image
is a family of bipolar fuzzy sets, where γ j+ ( vi ) = {( vj , mA + ( vj ))}∪{( vi , mA + ( vi )); mB + ( vi , vj ) = 0, i j } and γ j ( vi ) = {( vj , mA ( vj ))} ∪ {( vi , mA ( vi )); mB ( vi , vj ) = 0, i j }. Also by Definition 3.1,
PPT Slide
Lager Image
, i + j + , i j . Hence
PPT Slide
Lager Image
are independent sets of vertices (i.e no two vertices in
PPT Slide
Lager Image
are adjacent) for each j + = 1, 2,..., k, j = 1, 2,..., k′ . Then by remark 3.5, X ( G ) = ( X ( Gt ), X ( Gt′ )) = ( k, k′ ), where t = min { α + , α + L + } = max { X α+ , α + L + }, t′ = max { α , α L } = max { X α , α L }. Therefore, X ( G ) = Xf ( G ). □
Example 3.6. Consider the following bipolar fuzzy graph G = ( A,B ) and the crisp graphs G 0.4 , G 0.3 , G 0.2 , G 0.1 , G 0 , G −0.7 , G −0.5 , G −0.3 , G −0.1 given in Figures 7 , 8 corresponding to the values in the positive and negative level set of the bipolar fuzzy graph, L + = {0.1, 0.2, 0.3, 0.4}∪{0} and L - = {−0.7,−0.5,−0.3,−0.1}.
PPT Slide
Lager Image
PPT Slide
Lager Image
The fuzzy coloring is
PPT Slide
Lager Image
PPT Slide
Lager Image
Hence Xf ( G ) = ( Xf + ( G ), Xf ( G )) = (4, 4) and the crisp graphs coloring yields X ( G ) = ( maxX ( G α+ ), maxX ( G α )) = (4, 4).
PPT Slide
Lager Image
Definition 3.7. A bipolar fuzzy graph G = ( A,B ) is called a complete bipolar fuzzy graph on n vertices, denoted by Kn , if | V ( G ) |= n, xy E ( G ), mB + ( x, y ) = min ( mA + ( x ), mA + ( y )) and mB ( x, y ) = max ( mA ( x ), mA ( y )), for any distinct element x, y V ( G ).
Corollary 3.8. The bipolar fuzzy vertex chromatic number of complete bipolar fuzzy graph G = ( A,B ) is ( n, n ) , where n is the number of vertices of G, i.e. XV ( G ) = ( n, n ).
Proof . Consider the crisp graphs G α+ and G α , where α = max L and α + = min L + . Since G is a complete bipolar fuzzy graph, hence G α+ , G α are complete crisp graphs. Therefore, XV ( G ) = ( XV ( G α+ ), XV ( G α )) = ( n, n ). □
Corollary 3.9. The edge chromatic number of complete bipolar fuzzy graph G = ( A,B ) on n vertices is ( n, n ) , if n is odd and is ( n −1, n −1) , if n is even .
Proof . Consider the crisp graphs G α+ and G α , where α = max L and α + = min L + . Since G is a complete bipolar fuzzy graph, hence G α+ and G α are complete crisp graphs. Therefore, XE ( G ) = ( XE ( G α+ ), XE ( G α )) = ( n, n ), if n is odd and is equal ( n − 1, n − 1), if n is even. □
4. Conclusion
In this paper, we compute bipolar fuzzy vertex, edge, total chromatic number based on α + -cut, α -cut of a bipolar fuzzy graph whose edge and vertices both are bipolar fuzzy set. Also, we propose definition Eslahchi and Onagh [6] of bipolar fuzzy chromatic number and prove this two definition are equivalence.
Acknowledgements
The authors are extremely grateful to the Editor in Chief Prof. Cheon Seoung Ryoo and anonymous referees for giving them many valuable comments and helpful suggestions which helps to improve the presentation of this paper.
BIO
Atena Tahmasbpour
Department of Mathematics, Islamic Azad University, Central Tehran Branch, Tehran, Iran.
e-mail: atena.tahmasbpour@yahoo.com
Rajab Ali Borzooei is Professor of Math., Shahid Beheshti University of Tehran, Tehran, Iran. His research interests include Fuzzy Graphs Theory, Fuzzy logical algebras, BLalgebras, BCK and BCI-algebras.
Department of Mathematics, Shahid Beheshti University, Tehran, Iran.
e-mail: borzooei@sbu.ac.ir
References
Akram M. (2011) Bipolar fuzzy graphs Information Sciences 181 5548 - 5564    DOI : 10.1016/j.ins.2011.07.037
Ananthanarayanan M. , Lavanya S. (2014) Fuzzy graph coloring using alpha cuts International Journal of Engineering and Applied Sciences 4 23 - 28
Bartlett P. (2011) The chromatic number, Introduction to Graph Theory Mathcamp 1 - 5
Day A. , Pal A. (2012) Vertex coloring of a fuzzy graph using alpha cut IJMIE 2 340 - 352
Diestel R. (1997) Graph theory Springer New York, NY, USA 173
Eslahchi C. , Onagh B.N. (2006) Vertex-strength of fuzzy graphs International Journal of Mathematics and Mathematical Sciences Article ID 43614 2006 1 - 9    DOI : 10.1155/IJMMS/2006/43614
Firouzian S. , Nouri Jouybari M. (2011) Coloring fuzzy graphs and traffic light problem The Journal of Mathematics and Computer Science 2 431 - 435
Kishore A. , Sunitha M.S. (2013) Chromatic number of fuzzy graphs Annals of Fuzzy Mathematices Informatics 7 543 - 551
Kishore A. , Sunitha M.S. (2014) Strong chromatic number of fuzzy graphs Annals of pure and applied mathematics 7 52 - 60
Pal M. , Rashmanlou H. (2013) Irregular interval-valued fuzzy graphs Annals of Pure and Applied Mathematics 3 56 - 66
Poornima B. , Ramaswamy V. (2010) Total coloring of a fuzzy graph International Journal of Computational and Applied Mathematics 5 11 - 22
Rashmanlou H. , Samanta S. , Pal M. , Borzooei R.A. (2015) A study on bipolar fuzzy graphs Journal of Intelligent and Fuzzy Systems 28 571 - 580
Rashmanlou H. , Pal H. (2013) Antipodal interval-valued fuzzy graphs International Journal of Applications of Fuzzy Sets and Artificial Intelligence 3 107 - 130
Rashmanlou H. , Pal M. (2013) Balanced interval-valued fuzzy graph Journal of Physical Sciences 17 43 - 57
Rashmanlou H. , Pal M. (2013) Some properties of highly irregular interval-valued fuzzy graphs World Applied Sciences Journal 27 1756 - 1773
Rosenfeld A. (1975) Fuzzy graphs, Fuzzy sets and their applications Academic Press New York 77 - 95
Swaminathan S. (2012) Fuzzy graph applications of job allocation International Journal of Engineering and Innovative Technology 2 7 - 10
Samanta S. , Pal M. (2012) Irregular bipolar fuzzy graphs International Journal of Applications of Fuzzy Sets 2 91 - 102    DOI : 10.4018/ijfsa.2012040105
Talebi A.A. , Rashmanlou H. (2013) Isomorphism on interval-valued fuzzy graphs Annals of Fuzzy Mathematics and Informatics 6 47 - 58
Zadeh L.A. (1965) Fuzzy sets Information and Control 8 338 - 353    DOI : 10.1016/S0019-9958(65)90241-X
Zhang W.R. Bipolar fuzzy sets and relations: A computational frame work for cognitive modelling and multiagent decision analysis Proceeding of IEEE Conf. 305 - 309
Zhang W.R. Bipolar fuzzy sets Proceeding of Fuzzy-IEEE (1998) 835 - 840