Fuzzy colouring of m -polar fuzzy graph and its application

Abstract

In this article, a new idea of fuzzy coloring of m-polar fuzzy graph is presented while establishing the relationship between chromatic number of m-polar fuzzy graph and it’s underlying crisp graph. Some properties of m-polar fuzzy graph and new concepts of independently strong edge and independently weak edge in m-polar fuzzy graph are proved. The differences between fuzzy coloring of fuzzy graph and m-polar fuzzy graph are discussed. It is also shown that a m-polar fuzzy graph can be decomposed into m fuzzy graphs. Again, from m isomorphic fuzzy graph one can construct a m-polar fuzzy graph. A relation among chromatic numbers of m-polar fuzzy graph and m such graphs is established. Lastly a real life application of the fuzzy coloring is discussed.

Keywords

independently weak edges independently strong edges chromatic number

1. Introduction

A graph is used to present the inter connectedness of a system or network. In 1736, the great Swiss mathematician Euler first discussed the solution of the Konigsberg seven bridge problem. Graph theory has wide applications in different areas like electric network, computer network, road network, image capturing, scheduling problem, etc.

Zadeh [37] recognised the phenomena of vagueness and uncertainty of real life system and introduced fuzzy sets which changed the face of science and technology. In 1994, Zhang elaborated the fuzzy set concept and introduced the idea of bipolar fuzzy sets. Next Mordeson [25, 26] and In 2014, Chen et al. [9] introduced the notion of m-polar fuzzy sets as a generalization of bipolar fuzzy sets. Kafmann [23] was first to introduce the idea of fuzzy graph from Zadeh’s fuzzy relation. Later on Rosenfeld [21] gave the idea of fuzzy vertex, fuzzy edges and theoretical fuzzy graph concepts like paths, connectedness, cycle, etc. Bhutani and Rosenfeld introduced strong arc on fuzzy graph [4]. Nayeem and Pal [27] introduced shortest path problem on a network with imprecise edge weight. Samanta and Pal has introduced fuzzy planar graph [30] and Samanta et al. discussed fuzzy coloring of fuzzy graphs [29]. Yang et al. [36] introduced notes on bipolar fuzzy graphs. Then Talebi [35] studied on complement and isomorphism on bipolar fuzzy graphs. Later on Rashmanlou et al. [6–8 , 28] study on bipolar fuzzy graphs, bipolar fuzzy graphs with categorical properties, Domination in vague graphs and its applications, product vague graphs and its applications, New concepts of interval-valued intuitionistic (S; T)-fuzzy graphs and Cayley Interval-valued fuzzy graph and some results on vague graphs. Later on Ghorai and Pal introduced some operations, density on m-polar fuzzy graphs along with some useful properties of m-polar fuzzy graphs [10, 11]. They carried on an exhaustive study on the said graph and henceforth introduced faces and dual of m-polar fuzzy planar graphs [12, 13]. Akram and Adeel have also worked on m-polar fuzzy graphs and m-polar fuzzy line graphs [3]. Akram et al. studied certain type of edge on m-polar fuzzy graph [2]. Sahoo and Pal introduced the concept of intutionsitic fuzzy tolerance graph [31] and intuitionistic fuzzy graphs and degree, Intuitionistic fuzzy competition graphs [32, 33] and later on introduced embedding and genus of intuitionistic fuzzy graphs on spheres [34] and Karunambigai [22] introduced arcs in intuitionistic fuzzy graphs. Later on Mandal et al. discussed genus value of m-polar fuzzy graphs [24].

In this paper, a new concept of coloring of m-polar fuzzy graph using fuzzy color is introduced. The method of coloring is developed based on independently strong edge and independently weak edge. We have discussed some interesting properties on m-polar fuzzy graph as well, along with a detailed description of ‘strength cut graph’. Also, we have discussed some results on m-polar fuzzy chromatic number. At the end, we have shown the usefulness of this technique of m-polar fuzzy graph coloring through an application on metro railway system of Tokyo.

2. Preliminaries

In this section, we shortly recalled some basic definitions of undirected graphs, m-polar fuzzy graphs and other terms related to it. Let G = (V, E) be a graph where V (non-empty set) is called vertex set and E is called edge set. If no edge incident with a vertex, then the vertex is said to be isolated vertex, otherwise, it is said to be non-isolated vertex.

Vertex coloring of a graph or simply coloring of a graph is a way such that the adjacent vertices will received the different colors. The least number of colors which needed to color a given graph G is called chromatic number and it is denoted by χ (G).

Definition 1. [21] A fuzzy graph G = (V, σ, μ) with underlying crisp graph G^∗ = (V, E) where σ : V → [0, 1] is a fuzzy set in V and $μ : (\tilde{V^{2}}) \to [0, 1]$ is a fuzzy set in $\tilde{V^{2}}$ such that μ (a, b) ≤ inf {σ (a), σ (b)} for all $(a, b) \in \tilde{V^{2}}$ and μ (a, b) =0 for all $(a, b) \in (\tilde{V^{2}} - E)$ , 0 is the least element in [0, 1]. σ and μ are the fuzzy vertex set and fuzzy edge set of G respectively.

Starting from this and till the end of this paper [0, 1] ^m(m^th-power of [0, 1]) is taken to be a partial order set with point-wise order ≤, where m ∈ N and “ ≤ " means x≤ y ⇔ for each i = 1, 2 … m, p_i (x) ≤ p_i (y), where x, y ∈ [0, 1] ^m and p_i : [0, 1] ^m → [0, 1] is the i^th projection mapping.

First, the definition of m-polar fuzzy set is given by Chen et al. [9]. The definition of it is given below.

Definition 2. [24] A mapping B : D → [0, 1] ^m is said to be m-polar fuzzy set (or a [0, 1] ^m-set) and it is denoted by (D, B) where B = (p₁ ∘ B, p₂ ∘ B, … p_m ∘ B) where p_i ∘ B = i^th component of B. In particular case if we consider m = 3, then it is a 3-polar fuzzy set.

Definition 3. [11] An m-polar fuzzy graph G = (V, σ, μ) with underlying crisp graph G^∗ = (V, E) where σ : V → [0, 1] ^m is an m-polar fuzzy set in V and $μ : \tilde{V \times V} \to [0, 1]^{m}$ is an m-polar fuzzy set in $\tilde{V \times V}$ such that for each i = 1, 2, …, m, p_i ∘ μ (a, b) ≤ inf {p_i ∘ σ (a), p_i ∘ σ (b)} for all $(a, b) \in \tilde{V \times V}$ and μ (a, b) = 0 for all $(a, b) \in (\tilde{V \times V} - E)$ , (0 = (0, 0, …, 0) is the least element in [0, 1] ^m). p_i ∘ σ (a) and p_i ∘ μ (a, b) represents i^th component the degree of membership value of a vertex a and (a, b) edge of m-polar fuzzy graph.

Definition 4. [10] A complete m-polar fuzzy graph G = (V, σ, μ) is such that p_i ∘ μ (a, b) = inf {p_i ∘ σ (a), p_i ∘ σ (b)}, for all a, b ∈ V, i = 1, 2, …, m.

Example 1. An example of complete m-polar fuzzy graph is depicted in Fig. 1.

Fig. 1

Complete 3-polar fuzzy graph with four vertices.

Definition 5. [11] An m-polar fuzzy graph G = (V, σ, μ) is said to be strong if $p_{i} \circ μ (a, b) = \inf {p_{i} \circ σ (a), p_{i} \circ σ (b)},$ for all (a, b) ∈ E, i = 1, 2, …, m.

Example 2. The example of a strong m-polar fuzzy graph is presented in Fig. 2.

Fig. 2

Strong 3-polar fuzzy graph with four vertices.

Definition 6. [12] An m-polar fuzzy graph G = (V, σ, μ) is said to be bipartite if the vertex set V can be partitioned into two non-empty sets V₁ and V₂ such that for each i = 1, 2, … m, p_i ∘ μ (a, b) >0 if a, b ∈ V₁ or a, b ∈ V₂.

Throughout this paper G^∗ = (V, E) represent the underlying crisp graph and G is an m-polar fuzzy graph of G^∗ = (V, E).

3. Strength cut graph of m-polar fuzzy graphs

In this section, some basic definitions of strength cut graph is given and studied their few important properties.

For the m-polar fuzzy graph G = (V, σ, μ), an edge (a, b), a, b ∈ V is called independently strong if $\frac{1}{2} {p_{i} \circ σ (a) \land p_{i} \circ σ (b)} \leq p_{i} \circ μ (a, b), i = 1, 2, \dots, m$ . Otherwise, it is called independently weak edge. The strength of the edge (a, b) is defined by $p_{i} \circ I (a, b) = \frac{p_{i} \circ μ (a, b)}{p_{i} \circ σ (a) \land p_{i} \circ σ (b)}, i = 1, 2, \dots, m .$ Again, strength of a vertex a is considered as supremum value among all its membership values σ (a) and strengths I_(a,b) of edges (a, b) incident to a. Now, let θ_a=sup{I_(a,b)| (a, b) is an edge in G }. The strength of a vertex a ∈ V is denoted by I_a and defined by I_a = inf{θ_a, σ (a)}. Now strength cut graph of an m-polar fuzzy graph is defined below.

Definition 7. The α-cut (0 ≤ α ≤ 1) of an m-polar fuzzy graph G = (V, σ, μ) is a crisp graph G_α = (V_α, E_α) such that for i = 1, 2, …, m, V_α = {a ∈ V|p_i ∘ σ (a) ≥ α} and E_α = {(a, b) |p_i ∘ μ (a, b) ≥ α}.

Definition 8. Let G = (V, σ, μ) be an m-polar fuzzy graph. The α-strength cut graph (0 ≤ α ≤ 1) of G is defined as the crisp graph G^α = (V^α, E^α) such that V^α = {v ∈ V|p_i ∘ I_v ≥ α} and E^α = {(a, b), a, b ∈ V|p_i ∘ I_(a,b) ≥ α}

Example 3. Let us consider a 3-polar fuzzy graph (shown in Fig. 3) to illustrate α-strength cut graph.

Fig. 3

3-polar fuzzy graph.

The α (=0.4)-strength cut graph of 3-polar fuzzy graph of Fig. 3 is shown in Fig. 4.

Fig. 4

0.4-strength cut of 3-polar fuzzy graph of Fig. 3.

Fig. 5

3-polar fuzzy graph.

Theorem 1. Let G be an m-polar fuzzy graph. If 0 ≤ α ≤ β ≤ 1, then G^β ⊆ G^α.

Proof. Let G = (V, σ, μ) be an m-polar fuzzy graph and 0 ≤ α ≤ β ≤ 1. Now G^α = (V^α, E^α) where V^α = {v ∈ V|p_i ∘ I_v ≥ α} and E^α = {(a, b), a, b ∈ V|p_i ∘ I_(a,b) ≥ α}, i = 1, 2, …, m. G^β = (V^β, E^β) where V^β = {v ∈ V|p_i ∘ I_v ≥ β} and E^β = {(a, b), a, b ∈ V|p_i ∘ I_(a,b) ≥ β},i = 1, 2, …, m. To show G^β ⊆ G^α, let us consider a vertex x ∈ V^β. Then p_i ∘ I_x ≥ β This is, p_i ∘ I_x ≥ α as β ≥ α. Hence, x ∈ V^α. Similarly, for any arbitrary element (a, b) ∈ E^β, we can show that (a, b) ∈ E^α. Therefore, G^β ⊆ G^α. Now, we want to find the relationship between α-cut graph G_α and strength cut graph G^α of an m-polar fuzzy graph G.

Theorem 2. Let G be an m-polar fuzzy graph. If 0 ≤ α ≤ 1, then G_α ⊆ G^α.

Proof. Let G = (V, σ, μ) be an m-polar fuzzy graph. Let G_α = (V_α, E_α) such that V_α = {a ∈ V|p_i ∘ σ (a) ≥ α} and E_α = {(a, b), a, b ∈ V|p_i ∘ μ (a, b) ≥ α},i = 1, 2, …, m. Let us consider a, b ∈ V_α and (a, b) ∈ E_α. Then p_i ∘ σ (a) ≥ α, p_i ∘ σ (b) ≥ α, i = 1, 2, …, m and p_i ∘ μ (a, b) ≥ α, i = 1, 2, …, m. As α ≤ 1, we have $\frac{p_{i} \circ μ (a, b)}{p_{i} \circ σ (a) \land p_{i} \circ σ (b)} \geq α$ . Hence p_i ∘ I (a, b) ≥ α, i = 1, 2, …, m. So, (a, b) ∈ E^α. Therefore, for any edge of G_α, there exists an edge in G^α. Again from the definition of strength of vertices, V_α ⊆ V^α. Therefore, G_α ⊆ G^α.

4. Decomposition and Composition of m-polar fuzzy graph

4.1. Decomposition

From m-polar fuzzy graph, we can construct m fuzzy graphs taking their respective components. Let G be an m-polar fuzzy graph. We can construct the fuzzy graphs G₁, G₂, …, G_m in such a way that the graph G_i can be constructed by taking i^th component of the membership value of vertices and the edges of the m-polar fuzzy graph G. This can be elaborated by giving an example.

Example 4. Consider a 3-polar fuzzy graph G with underlying crisp graph G^∗ = (V, E) such that V = {a, b, c, d, e, f} and edges E = {ab, bc, cd, de, ef, af, ae, ad} where the membership values of the vertices and edges are given in Table 1:

Table 1
Membership value of 3-polar fuzzy graph G

Vertex Membership value

a (0.4, 0.5, 0.6)

b (0.3, 0.5, 0.7)

c (0.6, 0.8, 0.8)

d (0.5, 0.7, 0.8)

e (0.3, 0.5, 0.7)

f (0.6, 0.8, 0.8)

Vertex	Membership value
a	(0.4, 0.5, 0.6)
b	(0.3, 0.5, 0.7)
c	(0.6, 0.8, 0.8)
d	(0.5, 0.7, 0.8)
e	(0.3, 0.5, 0.7)
f	(0.6, 0.8, 0.8)

Edge	Membership value
ab	(0.2, 0.3, 0.4)
bc	(0.3, 0.4, 0.6)
cd	(0.2, 0.3, 0.4)
de	(0.1, 0.2, 0.4)
ef	(0.3, 0.4, 0.6)
af	(0.1, 0.3, 0.3)
ae	(0.3, 0.4, 0.4)
ad	(0.2, 0.2, 0.3)

Now we can construct three fuzzy graphs G₁, G₂, G₃ from the 3-polar fuzzy graph. The membership values of vertices and edges of the fuzzy graph G₁ are given in Table 2.

Table 2

Membership value of fuzzy graph G_1

Vertex	Membership value
a	0.4
b	0.3
c	0.6
d	0.5
e	0.3
f	0.6

Edge	Membership value
ab	0.2
bc	0.3
cd	0.2
de	0.1
ef	0.3
af	0.1
ae	0.3
ad	0.2

The membership values of vertices and edges of the fuzzy graph G₂ are shown in the Table 3:

Table 3

Membership value of fuzzy graph G_2

Vertex	Membership value
a	0.5
b	0.5
c	0.8
d	0.7
e	0.5
f	0.8

Edge	Membership value
ab	0.3
bc	0.4
cd	0.3
de	0.2
ef	0.4
af	0.3
ae	0.4
ad	0.2

The membership values of vertices and edges of the fuzzy graph G₃ are provided in Table 4.

Table 4

Membership value of fuzzy graph G_3

Vertex	Membership value
a	0.6
b	0.7
c	0.8
d	0.8
e	0.7
f	0.8

Edge	Membership value
ab	0.4
bc	0.6
cd	0.4
de	0.4
ef	0.6
af	0.3
ae	0.4
ad	0.3

The fuzzy graphs G₁, G₂, G₃, are shown in Fig 6. Note that all these graph are isomorphic in crisp sense.

Fig. 6

G₁, G₂, G₃ are the fuzzy graphs obtained from the 3-polar fuzzy graph shown in Fig. 5.

4.2. Composition

Let us consider m fuzzy graphs G₁, G₂, …, G_m whose underlying crisp graphs $G_{1}^{*}, G_{2}^{*}, \dots, G_{m}^{*}$ are isomorphic. Since we have m fuzzy graphs, we can think there are m places which can be filled by m objects. This can be done by m ! ways. Therefore, we can get m ! number of m-polar fuzzy graphs. This is explained in the following example.

Example 5. Let G₁, G₂, G₃ be three fuzzy graphs having same number of vertices and edges in Fig. 7 where the underlying crisp graphs $G_{1}^{*}, G_{2}^{*}, G_{3}^{*}$ are isomorphic. Let G_i = (V, σ_{G
_i}, μ_{G
_i}), i = 1, 2, 3.

Fig. 7

G₁, G₂, G₃ are the fuzzy graph.

Since, there are 3 fuzzy graphs G₁, G₂, G₃ so, we can arrange them in the following 3 ! =6 ways. Let these six graphs be denoted by H₁, H₂, …, H₆. H₁ = G₁G₂G₃

H₂ = G₂G₁G₃

H₃ = G₁G₃G₂

H₄ = G₃G₁G₂

H₅ = G₃G₂G₁

H₆ = G₂G₃G₁

All these arrangements are distinct and total number of arrangements is 6. The 3-polar fuzzy graphs are shown in Figs. 8–13.

Fig. 8

The first 3-polar fuzzy graph H₁.

Fig. 9

The second 3-polar fuzzy graph H₂.

Fig. 10

The third 3-polar fuzzy graph H₃.

Fig. 11

The fourth 3-polar fuzzy graph H₄.

Fig. 12

The fifth 3-polar fuzzy graph H₅.

Fig. 13

The sixth 3-polar fuzzy graph H₆.

Hence, from a set of m fuzzy graphs whose crisp graph are isomorphic, we can construct different m ! number of m-polar fuzzy graphs.

5. Fuzzy coloring

The coloring of m-polar fuzzy graph can be done using the concept of fuzzy coloring [29]. When two colors are mixed, a new color is created, But, when some colors are mixed with white color it decreases the density of the color. Let w unit of a color C_k is mixed with white color of amount (1 - w) unit. This is called the standard mixture of the color C_k. This is called fuzzy color with membership value w of the basic color C_k. As for example some basic colors are blue, green, red, black, etc.

Definition 9. Let us consider the basic color set be C = {C₁, C₂, …, C_n}, n ≥ 1. Let f : C ⟶ [0, 1] be a mapping. Then the color C_i with it’s membership value f (C_i) is a fuzzy set (C_i, f (C_i)) and this is a fuzzy color of the basic color C_i. ‘1’ will be the member value of the basic color.

Using above definition of fuzzy coloring, starting from the some basic colors we can introduce different types of fuzzy colors. When 0.8 units of blue is mixed with 0.2 units of white then we get “fuzzy blue" color and it is denoted by (blue,0.8). Similarly, if we add 0.6 units of blue color with 0.4 units of white color then it is also a fuzzy color and it is denoted by (blue,0.4). Note that, (blue,1) is a basic blue color.

5.1. Method of fuzzy coloring of m-polar fuzzy graph

In graph theory, vertices are colored by different colors if they are adjacent. Using fuzzy color, m-polar fuzzy graph can be colored. In this method, two vertices are colored by different basic colors if they are adjacent by an independently strong edge otherwise, they get different types of fuzzy colors.

Let G = (V, σ, μ) be a connected m-polar fuzzy graph and the set of basic colors be C = {C₁, C₂, …, C_n}. Here, independent strong and independent weak edges are two types of fuzzy edges. Independently strong edge are more important than independently weak edge. Based on these edges only, the m-polar fuzzy graph can be colored using fuzzy color. Therefore, an m-polar fuzzy graph can be classified into three groups, mentioned below:

All edges are independently strong.

Some edges are independently strong.

All edges are independently weak.

Case 1 m-polar fuzzy graph with all independently strong edges

If all the edges are independently strong edges of an m-polar fuzzy graph, then the coloring of m-polar fuzzy graph is same as ordinary graph coloring.

Case 2 m-polar fuzzy graph with some edges are independently strong

Let N (b) = {a_i ∈ V, i = 1, 2, …, n} be the set of all neighborhoods of b. In Fig. 14 we consider two vertices c, d such that (b, c), (b, d) are the independently strong edges incident to b and remaining all other edges are independently weak. At first we color the vertex b with some basic color (w, 1) and c by any other color (w₂, 1). In the same way, d will get a new color different from b. Now let us consider the vertex e for coloring. Note that (b, e) is an independently weak edge.

Fig. 14

The doted lines represent independently weak edges and plain lines represent independently strong edge.

Case 2.1 All the adjacent vertices of ‘e’ are not colored

Since, (b, e) is an independently weak edge, ‘e’ gets a fuzzy color. If we color ‘b’ by (w, 1) then ‘e’ can be colored by (w, f (w)) where f (w) is given by f (w) =1 - I_(b,w).

Case 2.2 All the vertices adjacent to ‘e’ are colored

If ‘e’ has an edge (e, h) which is independent strong, then ‘e’ can not get the color in which h is colored. Therefore, if (c_h, f (c_h)) is the color of h, then ‘e’ can be colored by any fuzzy color except c_h. If ‘e’ has some edges which are independently weak, namely (e, g_i), i = 1, 2, …, t. Then let us suppose that g_i gets the color (g_i, f (g_i)), i = 1, 2, …, t, where f (g_i) is the membership value of g_i, i = 1, 2, …, t. Now the color of ‘e’ can be found out. For i = 1, 2, …, m, A_i = min {p_i ∘ I_(e,g₁), p_i ∘ I_(e,g₂) …, p_m ∘ I_{(e,g_t)}} and for i = 1, 2, …, m, B_i = p_i ∘ I_(b,e). Let D = min {A₁, A₂, … A_m, B₁, B₂, … B_m}. If the color of g_p be (g_p, f (g_p), therefore (g_p, 1 - D) be the color of ‘e’.

Case 2.3 Some of the vertices which are adjacent to ‘e’ are colored

The vertices which are adjacent do not get effected by the color of ‘e’. So, the color which are used to color the adjacent vertices, will be considered for coloring of ‘e’. The method of coloring of ‘e’ is same as Case 2.2.

Case 3 m-polar fuzzy graph with all edges are independent weak edges

Let us consider any vertex a and consider any basic color say (C_a, 1). Then the vertices except ‘a’ will get some fuzzy color of basic color C_a. In this fuzzy color, the membership value can be calculated same as in Case 2.2.

Note: If we consider that the m-polar fuzzy graph is disconnected, then its has more than one connected components. Therefore each connected component can be colored by the above methods.

6. Chromatic number of m-polar fuzzy graph

The least number of basic colors which are required to color an m-polar fuzzy graph is called chromatic number of that m-polar fuzzy graph. It is denoted by γ (G), where G is the m-polar fuzzy graph.

Now, we consider three m-polar fuzzy graphs. The first m-polar fuzzy graph (shown in Fig. 19) contains all the independently weak edges and second graph (shown in Fig. 20) contains all independently strong edges and third graph (shown in Fig. 21) contains some independently weak edges or some independently strong edges.

In the first m-polar fuzzy graph (shown in Fig. 19), consider the vertex ‘a’ to be colored by the basic color (R, 1) and all other vertices by the fuzzy colors (R, 0. x), (R, 0. y), (R, 0. w), (R, 0. z) where x, y, w, z are all positive integers. Here since one basic color is used to color the m-polar fuzzy graph, therefore the chromatic number is 1.

Fig. 15

The doted lines represent independently weak edges.

Fig. 16

The plain lines represent independent strong edge.

Fig. 17

3-polar fuzzy graph and the corresponding colored graph.

Fig. 18

Fuzzy coloring of 3-polar fuzzy graph.

Fig. 19

Fuzzy coloring of fuzzy graph G₁.

Fig. 20

Fuzzy coloring of fuzzy graph G₂.

Fig. 21

Fuzzy coloring of fuzzy graph G₃.

In the second m-polar fuzzy graph (shown in Fig. 20) all the edges are independently strong. Therefore in this case, the chromatic number of the m-polar fuzzy graph is same as the underlying crisp graph.

Lastly, we consider an m-polar fuzzy graph (shown in Fig. 21) in which some edges are independently strong edges and some are independently weak. Here, edges ab, bd, de are independently strong and rest are independently weak edges. Here first we color the vertex ’b’ by anyone basic color and the remaining vertices incident to an independently strong edge on it, is color by two basic colors. Here the vertex ‘c’ is incidence to independently weak edges. So, the vertex ‘c’ is colored by fuzzy color and the membership values can be calculated by the strengths of independent weak edges. This method is discussed in details below- We consider the 3-polar fuzzy graph with 5 vertices. Here, the edges cd, cb are independently weak. The strengths of the edges cd and cb are 〈0.33, 0.5, 0.375〉 and 〈0.4, 0.25, 0.375〉 respectively. The minimum among them is 0.25. So, the vertex ‘c’ is colored by the fuzzy color (G, 0.75) and it is two chromatic.

From the above three examples we can see that the chromatic number of m-polar fuzzy graph is less than or equal to the chromatic number of the underlying crisp graph.

6.1. Difference between fuzzy coloring on fuzzy graph and m-polar fuzzy graph

From the discussion of decomposition and composition of m-polar fuzzy graph, we see that if an edge is independently strong in an m-polar fuzzy graph then it is also independently strong edge in all the fuzzy graphs. If an edge is independently weak in an m-polar fuzzy graph then it may become independently strong edge in a fuzzy graph constructed from the m-polar fuzzy graph by decomposition. In Fig. 5, we see that the edges (a, f), (d, e), (c, d), (a, d) are independently weak and the remaining edges are independently strong. But in Fig. 6, in the graph G₁ we see that (a, d) is an independently strong edge whereas (a, f), (c, d), (d, e) are independently weak edges and in the graph G₂, the edge (a, f) is independently strong while (c, d), (d, e), (a, d) are independently weak and in the graph G₃, (a, d), (a, f), (c, d), (d, e) all are independently strong edges.

Fig. 22

Toyko metro map.

Using the fuzzy coloring method of m-polar fuzzy graph, we see that the 3-polar fuzzy graph in Fig. 5 can be colored by using two basic colors B and R which is shown in Fig. 15. But, when we decomposed the 3-polar fuzzy graph into the fuzzy graphs G₁, G₂, G₃, we need either two basic colors or three basic colors to color the fuzzy graph. The coloring fuzzy graph is shown in Figs. 16–18.

The main reason behind this is that if an edge is independently strong in an m-polar fuzzy graph, then its remains independently strong in every decomposed fuzzy graphs but when some edges are independently weak, it may not remain weak in all the decomposed fuzzy graphs. Thus, we conclude the following theorem.

Theorem 3. The chromatic number of the m-polar fuzzy graph is always less than or equal to the chromatic number of the decomposed fuzzy graphs.

Proof. We know that an edge (a, b) in an m-polar fuzzy graph is said to be independently strong if $\frac{1}{2} {p_{i} \circ σ (a) \land p_{i} \circ σ (b)} \leq p_{i} \circ μ (a, b), i = 1, 2, \dots, m$ . Otherwise, it is called independently weak edge. So, if an edge say (a, b) is independently weak in an m-polar fuzzy graph then $\frac{1}{2} {p_{i} \circ σ (a) \land p_{i} \circ σ (b)} \leq p_{i} \circ μ (a, b)$ may not hold for some i where 1 ≤ i ≤ m. But, when we decompose the m-polar fuzzy graph into m fuzzy graphs then the edge (a, b) may be independently strong in one of the fuzzy graphs, say G_j, where 1 ≤ j ≤ m. Again, we know that two basic colors are needed to color a vertex when they are connected by an independently strong edge. Thus, we need two basic colors to color the vertices a and b in a fuzzy graph where as in m-polar fuzzy graph, we just need only one basic color to color them as there is an independently weak edge between them. This proves the theorem.

Theorem 4. Let G be an m-polar fuzzy graph and G^∗ be its underlying crisp graph then γ (G) ≤ χ (G^∗).

Proof. Let G = (V, σ, μ) be an m-polar fuzzy graph and G^∗ = (V, E) where E = {(a, b) : p_i ∘ μ (a, b) ≥0}, i = 1, 2, …, m be its underlying crisp graph. Let |V| = n and χ (G^∗) = r where r ≤ n. Therefore, G can have at most n independently strong edges. If there are exactly n independently strong edge in G then the chromatic number of the underlying crisp graph is equal to the chromatic number of the m-polar fuzzy graph. If an edge is independently strong, then two end vertices of the edge can be colored by two different basic colors. Hence, if G has less than ‘n’ number of independently strong edges, then γ (G) ≤ r. Therefore γ (G) ≤ χ (G^∗).

Note. If a crisp graph is complete then χ (G^∗) = n, where n is the number of vertices of the complete graph. If all the edges of the complete graph is independently strong, then γ (G) = n.

Theorem 5. If G is an m-polar fuzzy graph, then χ (G^0.5) = γ (G).

Proof. Let G = (V, σ, μ) be an m-polar fuzzy graph. If an edge is independently strong in G then it is also independently strong edge in G^0.5. So there exists an one to one correspondence between the independently strong edges of G and G^0.5. Thus, χ (G^0.5) = γ (G).

Theorem 6. Let G be an m-polar fuzzy graph. If 0 ≤ p ≤ q ≤ 1, then χ (G^q) ≤ χ (G^p).

Proof. We know that chromatic number of any subgraph of a crisp graph is less than or equal to the crisp graph. Also by theorem 1, if p ≤ q then G^q ⊆ G^p. So, we have χ (G^q) ≤ χ (G^p).

Theorem 7. If G is an m-polar fuzzy graph, then χ (G^∗) - γ (G) is the minimum number of independently weak edges in G, where G^∗ is the underlying crisp graph.

Proof. Let t = χ (G^∗) - γ (G). Then we have two cases,

Case 1 Let t > 0.

Let (a, b) be an edge in G^∗ and (a′, b′) be the corresponding edge in the m-polar fuzzy graph G. In the underlying crisp graph two color to color the vertices a and b, but in m-polar fuzzy graph two different basic colors are needed when they are connected by an independently strong edge. Again, if they are connected by independently weak edge they can get the fuzzy color of the same basic color. Hence, in m-polar fuzzy graph two end vertices are colored by fuzzy colors of the same basic color if, at least, the corresponding edge in m-polar fuzzy graph is independently weak edge. This shows that G has at least t = χ (G^∗) - γ (G) independently weak edges.

Case 2 t = 0.

Then χ (G^∗) = γ (G). This shows that all the edges of G are independent strong.

Hence χ (G^∗) - γ (G) is the minimum number of independently weak edges in m-polar fuzzy graph.

Note. If an m-polar fuzzy graph contains n vertices then it contains at most $\frac{n (n - 1)}{2} - χ (G^{*}) + γ (G)$ independently strong edges.

7. Application

In the real world, many problems involved multi-agents or multi-polar information or multi-objects. Compared to fuzzy graph, m-polar fuzzy graph is more accurate and exact. Here, we give an application of m-polar fuzzy graph coloring in the metro railway system of Tokyo.

In modern days, metro rail is one of the most useful transport in our daily life. In Toyko, if anybody wants to go from one metro station to another metro station, he/she can easily travel just by looking at the color of metro rail line. For example, if somebody wants to travel from Nakano to Toyocho metro station, he/she first see the color (Sky color) and then select the Tozai line and go easily. If somebody wants to travel from Nakano-Sakaue to Korakuen, he/she first needs to select the color red and the Marunouchi line to reach Yotsuya from Nakano-Sakaue and then select the emerald color and Namboku Line to reach Korakuen.

The entire metro network can be represented by an m-polar fuzzy graph. The stations are taken as vertices and rail tracks are considered as edges. But, the question is how one can measure the membership values of vertices and edges. Lot of parameters are associated with a station (vertex) and rail track (edge). The parameters related to stations are grouped into two sections listed below.

Passenger facilities likes

Lifts and escalators facilities.

Number of booking office.

No of entry and exit gates.

Service frequency (peak frequency, off peak frequency).

Public transport accessibility at the stations.

First aid/ medical facility.

Digital electronic display.

Drinking water.

Food court.

Wash rooms.

Water fountain.

Cleanliness.

Waiting rooms/Dormitory.

Bank ATM.

Wheelchair.

Condition of stations likes

Number of platforms.

Length of the platform.

Length of passageways.

Real time updates on train services, timings.

Efficient security checkers.

Token vending machine (TMV) and Add value machine(AVM).

Parking facilities.

Customer care centers.

CCTV.

Similarly, the parameters associated to rail track are listed below.

signal delay

track condition.

Based on these parameters we have calculated the membership value of vertices and edges of the graph. Since, the facilities of a station are grouped into two sections so the membership value of a vertex is of two points and the resultant graph becomes a 2-polar fuzzy graph.

Let us consider five cities Ikebukuro, Otemachi, Tokyo, Shibuya, Skinjuku and their corresponding 2-polar fuzzy graph shown in Fig. 23. Based on independently weak edges and independently strong edges, we color the 2-polar fuzzy graph shown in Fig. 24.

Fig. 23

2-polar fuzzy graph with 5 vertices.

Fig. 24

Complete graph with 5 vertices.

Here, we see that this is a complete graph with five vertices and to color the graph through independently weak and independently strong edges, we just need three basic colors which is less than the number of colors required to color the underlying crisp graph K₅.

8. Conclusions

In this paper, we defined complete m-polar fuzzy graph, strength cut graph of m-polar fuzzy graph and discussed the relationship between the chromatic number of m-polar fuzzy graph and its underlying crisp graph. Here, we also shown that an m-polar fuzzy graph can be decomposed into m fuzzy graphs and from m fuzzy graphs whose crisp graph are isomorphic, we can construct m! number of m-polar fuzzy graphs. We will extend our research work to define fractional coloring on m-polar fuzzy graph and it’s properties along with real life application.

Footnotes

Acknowledgements

Financial support of first author offered by University Grants commission, New Delhi, India (UGC Ref.No:1215/CSIR-UGC NET DEC.2016) is thankfully acknowledged. The authors are thankful to the editor-in-chief and all of the reviewers for their valuable comments and suggestions to improve the paper.

References

Ananthanarayanan and

Lavanya , Fuzzy graph coloring using a-cut, International Journal of Engineering and Applied Sciences 4(10) (2014), 23–28.

Akram and

Adeel , M-polar fuzzy graphs and m-polar fuzzy line graphs, J Discrete Math Sci Cryptogr (2017), 1597–1617.

Akram ,

Wassem and

W.A.

Dudek , Certain types of edge m-polar fuzzy graph, Iran J Fuzzy Syst (2016). (in press)

K.R.

Bhutani and

Rosenfeld , Strong arcs in fuzzy graph, Inf Sci 152 (2003), 319–322.

K.R.

Bhutani and

Abdella , On M-strong fuzzy graphs, Information Sciences 155 (2003), 103–109.

A.R.

Borzooei and

Rashmanlou , Domination in vague graphs and its applications, Journal of Intelligent and Fuzzy Systems 29 (2015), 1933–1940.

A.R.

Borzooei and

Rashmanlou , Cayley intervalvalued fuzzy graph, UPB Sci Bull, Series A 78(3) (2016), 83–94.

A.R.

Borzooei and

Rashmanlou , More results on vague graphs UPB Sci Bull, Series A 78(1) (2016), 109–122.

Chen ,

Li ,

Ma and

Wang , M-polar fuzzy sets: An extension of bipolar fuzzy sets, Hindwai Publishing Corporation, The Scientific World Journal (2014), 8. Article Id 416530. https://dx-doi-org.web.bisu.edu.cn/10.1155/2014-416530

10.

Ghorai and

Pal , On some operations and density of m-polar fuzzy graphs, Pac Sci Rev A Nath Sci Eng 17(1) (2015), 14–22.

11.

Ghorai and

Pal , Some properties of m-polar fuzzy graphs, Pac Sci Rev A Nath Sci Eng 18 (2016), 38–46.

12.

Ghorai and

Pal , A study on m-polar fuzzy planar graphs, Int J Comput Sci Math 7(3) (2016), 283–292.

13.

Ghorai and

Pal , Faces and dual of m-polar fuzzy planner graphs, J Intell Fuzzy Syst 31 (2016), 2043–2049.

14.

Ghorai and

Pal , Planarity in vague graphs with application, Acta Mathematica Academiae Paedagogiace Nyregyhziensis 33(2) (2017), 1–21.

15.

Rashmanlou ,

Samanta ,

Pal and

A.R.

Borzooei , A study on bipolar fuzzy graphs, Journal of Intelligent and Fuzzy Systems 28(2) (2015), 571–580.

16.

Rashmanlou ,

Samanta ,

Pal and

A.R.

Borzooei , Bipolar fuzzy graphs with categorical properties, International Journal of Computational Intelligence Systems 8(5) (2015), 808–818.

17.

Rashmanlou ,

Samanta ,

Pal and

A.R.

Bor-zooei , Product of Bipolar fuzzy graphs and their degree, International Journal of General Systems. 10.1080/03081079.2015.1072521

18.

Rashmanlou and

A.R.

Borzooei , Domination in vague graphs and its applications, Journal of Intelligent and Fuzzy Systems 29 (2015), 1933–1940.

19.

Rashmanlou and

A.R.

Borzooei , New concepts of interval-valued intuitionistic (S; T)-fuzzy graphs, Journal of Intelligent and Fuzzy Systems 30 (2016), 1893–1901.

20.

Rashmanlou and

A.R.

Borzooei , Vague graphs with application, Journal of Intelligent and Fuzzy Systems 30 (2016), 3291–3299.

21.

Rosenfeld , Fuzzy Graphs, Fuzzy sets and their Application. Academic Press, New York, 1975, pp. 77–95.

22.

G.M.

Karunambigai ,

Parvathi and

Buvaneswari , Arcs in intuitionistic fuzzy graphs, 8th Int Workshop on IFSs, Banska Bystrica 18(4) (2012), 48–58.

23.

Kauffman , Introduction a la Theorie des Sousemsembles Flous, Mansson et Cie, 1, 1973.

24.

Mandal ,

Sahoo ,

Ghorai and

Pal , Genus value of m-polar fuzzy graphs, Journal of Intelligent and Fuzzy Systems 34(3) (2017), 1947–1957.

25.

J.N.

Mordeson and

P.S.

Nair , Operation on fuzzy graphs, Inf Sci 79(3-4) (1994), 159–170.

26.

J.N.

Mordeson and

P.S.

Nair , Fuzzy graphs and fuzzy hyper-graphs, 2nd edn, Physica Verlag, Heidelberg, 1998.

27.

Md.S.

Nayeem Abu and

Pal , Shortest path problem on a network with imprecise edge weight, Fuzzy Optimization and Decision Making 4 (2005), 293–312.

28.

Rosenfeld , Fuzzy Graphs, Fuzzy sets and their Application, Academic Press, New York, 1975, pp. 77–95.

29.

Samanta ,

Pramanik and

Pal , Fuzzy colouring of fuzzy graphs, Afrika Mathematika 27 (2016), 37–50.

30.

Samanta and

Pal , Fuzzy planar graph, IEEE Transaction on Fuzzy Systems 23 (2015), 1936–1942.

31.

Sahoo and

Pal , Intuitionistic fuzzy tolerance graph with application, Journal of Applied Mathematics and Computing 55 (2016), 495–511.

32.

Sahoo and

Pal , Intuitionistic fuzzy graphs and degree, Journal of Intelligent and Fuzzy Systems 32(1) (2016), 1059–1067.

33.

Sahoo and

Pal , Intuitionistic fuzzy competition graphs, J ApplMath Comput 52 (2016), 37–57.

34.

Sahoo ,

Ghorai and

Pal , Embedding and genus of intuitionistic fuzzy graphs on spheres, Journal of Multiple-Valued Logic and Soft Computing 31 (2018), 139–154.

35.

A.A.

Talebi and

Rashmanlou , Complement and isomorphism on bipolar fuzzy graphs, Fuzzy Information and Engineering 6 (2014), 505–522.

36.

L.H.

Yang ,

G.S.

Li ,

Yang and

Lu , Notes on "bipolar fuzzy graphs", Information Sciences 242 (2013), 113–121.

37.

L.A.

Zadeh , Fuzzy sets, Inf Control (1965), 338–353.

Fuzzy colouring of m -polar fuzzy graph and its application

Abstract

Keywords

1. Introduction

2. Preliminaries

4.1. Decomposition

Table 1 Membership value of 3-polar fuzzy graph G Vertex Membership value a (0.4, 0.5, 0.6) b (0.3, 0.5, 0.7) c (0.6, 0.8, 0.8) d (0.5, 0.7, 0.8) e (0.3, 0.5, 0.7) f (0.6, 0.8, 0.8)

5.1. Method of fuzzy coloring of m-polar fuzzy graph

Footnotes

Acknowledgements

References

Table 1
Membership value of 3-polar fuzzy graph G

Vertex Membership value

a (0.4, 0.5, 0.6)

b (0.3, 0.5, 0.7)

c (0.6, 0.8, 0.8)

d (0.5, 0.7, 0.8)

e (0.3, 0.5, 0.7)

f (0.6, 0.8, 0.8)