Fuzzy fractional coloring of fuzzy graph with its application

Abstract

In this article, a new idea of fuzzy fractional coloring of fuzzy graph is presented and fuzzy fractional chromatic number is defined. A relationship between fuzzy fractional chromatic number and fuzzy fractional clique number is established. Some properties of fuzzy chromatic number of fuzzy graphs and fuzzy fractional chromatic number of fuzzy graphs are proved and the concept of k-strong adjacent vertices is introduced. Fuzzy chromatic number and fuzzy fractional chromatic number have been calculated on lexicographic product of two fuzzy graphs. Also, fuzzy chromatic number, independence number and fuzzy fractional chromatic number have been investigated on disjoint union of two fuzzy graphs. Lastly, a real life application of fuzzy fractional coloring on fuzzy graph is discussed.

1 Introduction

A graph is used to present the inter connection of a system or network. Its foundation was laid by famous Swiss Mathematician Euler in 1736, when he discussed the solution of the Konigsberg seven bridge problem. It has become a tradition to maintain that there are applications of graph theory to different areas like electric network, computer network, road network, image capturing, scheduling problem, etc. A graph theory has an intuitive and aesthetic appeal because of the diagrammatic representation. One of the major part of graph theory is graph coloring. The most significant and well known subjects in combinatorial optimization and discrete domain is graph coloring. A lot of real life applications can be displayed and tackled by graph coloring. Some of the fascinating applications like wiring of printed circuits, loading problems, resource task issue, frequency assignment problem, a wide variety of scheduling problems and computer register allocation. A vertex coloring of a graph is an allocation of colors to all vertices of the graph, one color to each vertex, so that if two vertices are adjacent then they get different colors and the total number of used colors is to be minimized. One of the attractive and important extensions of graph coloring is fuzzy graph coloring.

In 1965, Zadeh (1965) recognized the phenomena of vagueness and uncertainty of real life system and introduced fuzzy set which changed the face of science and technology. In 1994, Zhang elaborated the fuzzy set concept and introduced the idea of bipolar fuzzy set. Chen et al. (2014) introduced the notion of m-polar fuzzy set as a generalization of bipolar fuzzy set. Kauffman (1973) was first to introduce the idea of fuzzy graph from Zadeh’s fuzzy relation. Later on Rosenfeld (1975) gave the idea of fuzzy vertex, fuzzy edges and theoretical fuzzy graph concepts like paths, connectedness, cycle, etc. Many variations of the concepts and definitions are suggested thereafter, mostly under the degree of fuzzy vertices, fuzzy paths, fuzzy trees, fuzzy sub-graphs, complement of a fuzzy graph in Mordeson and Nair (2000); Sunitha and Mathew (2013). Mordeson and Nair (1994) introduced fuzzy graph and fuzzy hypergraphs. Nagoorgani and Malarvizhi (2008) introduced isomorphism on fuzzy graphs. Anjali and Mathew (2015) introduced blocks and stars in fuzzy graphs. Bhutani and Rosenfeld (2003) introduced strong arc on fuzzy graph. Next, Bhutani and Battou (2003) studied on M-strong fuzzy graphs. Sunitha and Kumar (2002) introduced complement of fuzzy graph. Mathew and Sunitha introduced fuzzy graphs: Basics, Concepts and Applications in Mathew and Sunitha (2012). Eslahchi and Onagh (2006) studied on vertex strength of fuzzy graphs. Ananthanarayanan and Lavanya (2014) introduced fuzzy graph coloring using $\alpha$-cut. Radha and Arumugam (2015) studied on lexicographic products of two fuzzy graphs. Samanta and Pal (2015) has introduced fuzzy planar graph and Samanta et al. (2016) discussed fuzzy coloring of fuzzy graphs. Mũnoz et al. (2005) modeled and solved two different fuzzy graph coloring problems by generalizing the classical concept of the (crisp) chromatic number of a graph. Finally Rosyida et al. (2015) proposed an algorithm to find fuzzy chromatic set of fuzzy graphs. In their method, the fuzzy chromatic set of a fuzzy graph is constructed through its $\delta$-chromatic number. Later on, Rosyida et al. (2019) studied on fuzzy chromatic number of union of fuzzy graphs: an algorithm, properties and its application. Then Talebi and Rashmanlou (2014) studied on complement and isomorphism on bipolar fuzzy graphs. Next, they studied complement and isomorphism on bipolar fuzzy graphs in Talebi and Rashmanlou (2013). Rashmanlou et al. (2015a, b) studied on bipolar fuzzy graphs as well as categorical properties of bipolar fuzzy graphs. Yang et al. (2013) introduced generalized bipolar fuzzy graphs. Later on, Ghorai and Pal introduced m-polar fuzzy graph by extending the membership value of vertices and edges from a single value to m values. Each of the m values has separate meaning. They carried on their study on density on m-polar fuzzy graphs (Ghorai and Pal2015) along with some useful properties of m-polar fuzzy graphs (Ghorai and Pal2016a). Ghorai and Pal (2016b) carried on an exhaustive study on the said graph and introduced some properties on m-polar fuzzy planar graph. Later on, they introduced faces and dual of m-polar fuzzy planar graphs in Ghorai and Pal (2016c) and planarity in vague graphs with application in Ghorai and Pal (2017). Next, Akram and Adeel (2017) have also worked on m-polar fuzzy graphs and m-polar fuzzy line graphs. Akram et al. (2016) studied certain type of edges on m-polar fuzzy graph. Sahoo and Pal (2016a, b) introduced the concept of intutionsitic fuzzy tolerance graph and product intuitionistic fuzzy graphs and their degree. Later on Mandal et al. (2017) discussed genus value of m-polar fuzzy graphs. Recently, Chen et al. (2019) investigated an improved spectral graph partition intelligent clustering algorithm for low-power wireless network and most recently Selvi and Amutha (2020) introduced study on harmonious chromatic number of total graph of central graph of generalized Petersen graph.

In this paper, we have introduced k-strongly adjacent vertices and fuzzy fractional clique in fuzzy graphs. The method of fuzzy fractional coloring on fuzzy graphs is developed based on strongly adjacent vertices along with detailed description by an example. Also, we have presented a relationship between fuzzy fractional chromatic number and fuzzy fractional clique number of fuzzy graph. Some results on chromatic number and fuzzy fractional chromatic number are studied for fuzzy graph. An application is also provided at the end of the paper.

2 Preliminaries

In this section, we shortly recalled some basic definitions of undirected graphs, 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 (empty or non-empty set) 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 $\chi (G)$.

Definition 1

(Zadeh 1965) A fuzzy set A on the universal set X is characterized by a mapping $m:X \rightarrow [0,1]$, which is called the membership function. A fuzzy set is denoted by $A=(X,m)$.

Definition 2

( Kauffman1973) A fuzzy graph is a triplet $G=(V,\sigma ,\mu )$ with underlying crisp graph $G^*=(V,E)$ where $\sigma : V\rightarrow [0,1]$ is a fuzzy set in V and $\mu :{\widetilde{V^{2}}}\rightarrow [0,1]$ is a fuzzy set in ${\widetilde{V^{2}}}$ such that $\mu (a,b)\le inf\{ \sigma (a), \sigma (b)\}$, for all $(a,b)\in {\widetilde{V^{2}}}$ and $\mu (a,b)=0$, for all $(a,b)\in (\widetilde{{V^{2}}}-E)$. Here $\sigma$ and $\mu$ are the membership values of fuzzy vertex and fuzzy edge of G respectively.

Definition 3

( Sunitha and Mathew 2013) The fuzzy graph $H=(V_1,\sigma _1,\mu _1)$ is said to be a fuzzy subgraph of $G=(V,\sigma ,\mu )$ if $V_1\subseteq V$, $\sigma _1(a)=\sigma (a)$ for all $a\in V_1$ and $\mu _1(a,b)=\mu (a,b)$ for all $(a,b)\in {\widetilde{V_1^{2}}}$.

Definition 4

( Samanta et al. 2016) Let $G=(V, \sigma ,\mu )$ be a fuzzy graph. Two distinct vertices a and b in V are said to be strongly adjacent if $\frac{1}{2} min\{\sigma (a) ,\sigma (b)\}\le \mu (a,b)$. Otherwise, they are said to be non-strongly adjacent vertices.

It can be easily verified that strongly adjacent is a symmetric relation.

Definition 5

(Samanta et al. 2016) The strength of the edge (a, b) is defined by

$$\begin{aligned} I(a,b)=\frac{ \mu (a,b)}{\sigma (a) \wedge \sigma (b)}. \end{aligned}$$

Note 1

$0\le I(a,b)\le 1$, for all $(a,b)\in {E}$.

Again, strength of a vertex a is considered as supremum value among all its membership values $\sigma (a)$ and strengths $I_{(a,b)}$ of edges (a, b) incident to a.

Now, let $\theta _a$=$\sup \{I_{(a,b)}|(a,b)$ is an edge in G }. The strength of a vertex $a\in V$ is denoted by $I_a$ and defined by $I_a$ = $\inf \{\theta _a,\sigma (a)\}$. Now strength cut graph of a fuzzy graph is defined as follows.

Definition 6

(Eslahchi and Onagh 2006) The $\alpha$-cut $(0\le \alpha \le 1)$ of a fuzzy graph $G=(V,\sigma ,\mu )$ is a crisp graph $G_\alpha =(V_\alpha ,E_\alpha )$ such that $V_\alpha =\{a\in V|\sigma (a)\ge \alpha \}$ and $E_\alpha =\{(a,b)|\mu (a,b)\ge \alpha \}$.

Definition 7

( Samanta et al. 2016) Let $G=(V,\sigma ,\mu )$ be a fuzzy graph. The $\alpha$-strength cut graph $(0\le \alpha \le 1)$ of G is defined as the crisp graph $G^{\alpha }=(V^{\alpha },E^{\alpha })$ such that $V^{\alpha }=\{v\in V| I_v \ge \alpha \}$ and $E^{\alpha }=\{(a,b),a,b\in V| I_{(a,b)}\ge \alpha \}$.

Fig. 1

Fuzzy graph

Fig. 2

0.4-Strength cut of the fuzzy graph of Fig. 1

Example 1

Let us consider the fuzzy graph (as shown in Fig. 1) to illustrate $\alpha$-strength cut graph.

The $\alpha (=0.4)$-Strength cut graph of the fuzzy graph of Fig. 1 is shown in Fig. 2.

Definition 8

( Talebi and Rashmanlou 2013) Let us consider two fuzzy graphs $G_1=(V_1, \sigma _1,\mu _1)$ and $G_2=(V_2, \sigma _2,\mu _2)$ with underlying crisp graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ respectively. A homomorphism between $G_1$ and $G_2$ is a mapping $\phi : V_1\rightarrow V_2$ such that

• 1. $\sigma _1(a)\le \sigma _2(\phi (a))$, for all $a\in V_1$.

• 2. $\mu _1(a,b) \le \mu _2((\phi (a),\phi (b)))$, for all $(a,b)\in {E_1}$.

Definition 9

(Nagoorgani and Malarvizhi 2008) Let $G_1=(V_1, \sigma _1,\mu _1)$ and $G_2=(V_2, \sigma _2,\mu _2)$ be two fuzzy graphs with underlying crisp graphs $G_1=(V_1,E_1)$ and $G_2=(V_2, E_2)$ respectively. An isomorphism between $G_1$ and $G_2$ is a bijective mapping $\phi : V_1\rightarrow V_2$ such that

• 1. $\sigma _1(a)= \sigma _2(\phi (a))$, for all $a\in V_1$

• 2. $\mu _1(a,b) = \mu _2((\phi (a),\phi (b)))$, for all $(a,b)\in {E_1}$

It is denoted by $G_1\cong G_2$.

Definition 10

( Samanta et al. 2016) Let $G=(V, \sigma ,\mu )$ be a fuzzy graph. In G, the set of pairwise strongly non-adjacent vertices is called an independent set. The size of the largest independent set of G is called independence number of G and it is denoted by $\alpha (G)$.

Now, independent sets, independence number of the fuzzy graph in Fig.3 have been described.

Fig. 3

A fuzzy graph G

Here all the edges are strongly incident to the vertices.

In Fig. 3, the independent sets are $\{a,g\},\{a,c\},\{a,f\},\{b,e,d\},\{b,g\},\{c,e\},\{d,f\}$. Among all the independent sets in G, $\{b,e,d\}$ is the largest independent set in G and therefore $\alpha (G)=3$.

Definition 11

( Mũnoz et al. 2005) A proper n coloring is a mapping on vertices of a fuzzy graph that allots a colors to a vertex from a set of n colors in such a way that strongly adjacent vertices will get distinct color.

Definition 12

(Samanta et al. 2016) Let us consider the basic color set be

$C=\{C_1,C_2,\ldots ,C_n\},n\ge 1$. Let $f:C\longrightarrow [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. The least number of basic colors which are required to color a fuzzy graph is called chromatic number of that fuzzy graph. It is denoted by $\gamma (G)$, where G is the fuzzy graph.

Definition 13

(Rosyida et al. 2019) Let $G=(V, \sigma , \mu )$ be a fuzzy graph with n vertices. A fuzzy chromatic number of G, denoted by $\tilde{\chi }(G)$ is a fuzzy set,

$$\begin{aligned} \tilde{\chi }(G)=\{(k, L_{\tilde{\chi }}(k)): k=1, 2, \ldots , n\} \end{aligned}$$

where the value $L_{\tilde{\chi }}(k)= \max \{1-\delta : \delta \in [0, 1], \chi ^{\delta }(G)=k\}$ represents a degree of membership of number k in fuzzy chromatic number $\tilde{\chi }$.

3 $k-$ Strong adjacent vertices, lexicographic product and disjoint union of two fuzzy graphs

3.1 $k-$Strong adjacent vertices

Now, from Definition 4 we can decide whether two vertices are strongly adjacent or not. Here we will discuss how two vertices can be made strongly adjacent. In this regard, we will give a definition of k-strong adjacent vertices. This definition will enable us to make non-strongly adjacent vertices into strongly adjacent vertices.

Definition 14

Let $G=(V, \sigma ,\mu )$ be a fuzzy graph. Two vertices a and b in G are said to be k-strong adjacent if $\frac{1}{k} \min \{\sigma (a),\sigma (b)\}\le \mu (a,b)$, $k\in \mathbb {N}$.

Note 2

It can be easily verified that strongly k-adjacent is a symmetric relation.

Fig. 4

Fuzzy graph

Example 2

Here we will describe how two vertices in Fig. 4 can be made strongly adjacent.

In Fig. 4, the vertices c, d are not strongly adjacent. But, it can be made strongly adjacent if we choose a suitable value of k. Consider the edge (c, d). If we choose $k=4$, then $\frac{1}{4} \min \{\sigma (c),\sigma (d)\}=0.1= \mu (c,d)$. Therefore, c and d becomes strongly adjacent. Thus for $k=4$, all the vertices becomes strongly adjacent.

For a suitable value of k, the number of strongly adjacent edges in a fuzzy graph is equal to the number of edges in the underlying crisp graph.

3.2 Lexicographic product of two fuzzy graphs

Here we will recall the lexicographic product of two fuzzy graphs.

Definition 15

( Radha and Arumugam 2015) Let $G_1=(V_1, \sigma _1,\mu _1)$ and $G_2=(V_2, \sigma _2,\mu _2)$ be two fuzzy graphs whose underlying crisp graphs are $G_1^*=(V_1,E_1)$ and $G_2^*=(V_2,E_2)$ respectively. Then the lexicographic product of $G_1$ and $G_2$ is denoted by $G_1\circ G_2$ and is defined by $G=(V,\sigma ,\mu )$ where the underlying crisp graph is $G^*=(V,E)$, $V=V_1\times V_2$ and $E=\{(x_1,y_1)(x_2,y_2)|(x_1,x_2)\in E_1 \ and \ (y_1,y_2)\in E_2\, or\, x_1=x_2\ and\ (y_1,y_2)\in E_2\}$ and the membership values are given by $\sigma (x,y)=\sigma _1(x)\wedge \sigma _2(y), \forall (x,y)\in V_1\times V_2$ and

$$\begin{aligned} \mu ((x_1,y_1)(x_2,y_2))=\left\{ \begin{array}{llll} \mu _1(x_1,x_2) \wedge \mu _2(y_1,y_2), &{} \text{ if } \quad (x_1,x_2) \in E_1 \quad and \quad (y_1,y_2) \in E_2 \\ \sigma _1(x_1) \wedge \mu _2(y_1,y_2), &{} \text{ if } \quad x_1=x_2 \quad and \quad (y_1,y_2) \in E_2 \\ \end{array}\right. \end{aligned}$$

We explain the the concept of lexicographic product of two fuzzy graphs in the following example.

Fig. 5

Fuzzy graphs $G_1$ and $G_2$

Example 3

Let us consider two fuzzy graphs $G_1$ and $G_2$ having four and three vertices of Fig. 5 (a) and (b) respectively.

The corresponding lexicographic product of $G_1$ and $G_2$ is given by Fig. 6and lexicographic product of $G_2$ and $G_1$ is given by Fig. 7.

From the Fig. 6and Fig. 7, we can say that lexicographic product is not commutative.

Fig. 6

Lexicographic product of $G_1$ and $G_2$, i.e. the graph $G_1 \circ G_2$

Fig. 7

Lexicographic product of $G_2$ and $G_1$, i.e. the graph $G_2 \circ G_1$

3.3 Disjoint union of two fuzzy graphs

Here we will recall the disjoint union of two fuzzy graphs.

Definition 16

(Sunitha and Kumar 2002) Let $G_1=(V_1,\sigma _1,\mu _1)$ and $G_2=(V_2,\sigma _2,\mu _2)$ be two fuzzy graphs whose underlying crisp graphs are $G_1^*=(V_1,E_1)$ and $G_2^*=(V_2,E_2)$ respectively with $V_1\cap V_2=\emptyset$. Then disjoint union of $G_1$ and $G_2$ is denoted by $G_1\sqcup G_2$ and is defined by

$$\begin{aligned} (\sigma _1\sqcup \sigma _2)(x)= \left\{ \begin{array}{ll} \sigma _1(x) &{} \text{ if } x \in V_1-V_2 \\ \sigma _2(x) &{} \text{ if } x \in V_2-V_1 \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} (\mu _1 \sqcup \mu _2)(x,y)= \left\{ \begin{array}{ll} \mu _1(x,y) &{} \text{ if } (x,y) \in E_1- E_2 \\ \mu _2(x,y) &{} \text{ if } (x,y) \in E_2- E_1 \end{array} \right. \end{aligned}$$

Example 4

The concept of disjoint union of two fuzzy graphs is illustrated in this example (Figs. 8, 9).

Fig. 8

Two fuzzy graphs $G_1$ and $G_2$

Fig. 9

Disjoint union of $G_1$ and $G_2$

Note 3

The fuzzy graphs G and H are the subgraphs of the disjoint union $G\sqcup H$.

4 Fuzzy fractional coloring and fuzzy fractional clique

4.1 Fuzzy graph coloring and homomorphism

The n-coloring of a fuzzy graph G (denoted by $\gamma (G)=n$ ) can be thought of as a way of assigning one color for each vertices, from a set of n colors in such a way that two strong adjacent vertices will receive different colors. It can be defined in another way by using the idea of homomorphism of a fuzzy graph.

A proper n-coloring of a fuzzy graph can be defined as a fuzzy graph homomorphism from G to $K_n$ in such a way that the vertices which get the same color in G will map to a single vertex in $K_n$. Since no vertex in $K_n$ is adjacent to itself, no adjacent vertices in G will get the same color.

In a proper coloring, if we take the inverse image of a single vertex in $K_n$, this will get the set of all vertices in G with a certain color. It will always be an independent set. Thus, the chromatic number for simply coloring of a fuzzy graph is the smallest number of independent set which is required to cover the vertex set of the fuzzy graph.

Note 4

Here, fuzzy chromatic number of a fuzzy graphs means simply chromatic number of fuzzy graphs. Therefore, $\gamma (G)$ is called fuzzy chromatic number of a fuzzy graph G or simply chromatic number of fuzzy graph G.

Theorem 1

If G and H are two fuzzy graphs such that $\gamma (H)=n$, then $G\circ K_n$ is a fuzzy subgraph of $G\circ H$.

Proof

If $\gamma (H)=n$, then $K_n$ is a fuzzy subgraph of H. Now $G\circ K_n$ is a fuzzy subgraph of $G\circ H$ as $K_n$ is contained in H and the number of vertices and edges in $G\circ K_n$ is less than or equal to the number of vertices and edges in $G\circ H$. The membership values of vertices and edges of $G\circ K_n$ are also less than or equal to the membership values of vertices and edges of $G\circ H$. Hence, $G\circ K_n$ is a subgraph of $G\circ H$. $\square$

Now, we generalize the concept of simply coloring to fuzzy fractional coloring (or a set of coloring). Using this we will define fuzzy fractional chromatic number which may take non-integer values.

4.2 Fuzzy fractional coloring

Let G be a given fuzzy graph and consider two integers p and q such that $0<q\le p$. A proper p/q coloring is a mapping that allots vertices to a set of q distinct colors from a set of p colors in such a way that adjacent vertices will get disjoint arrangements sets of color. Hence, simply coloring or n-coloring is same as n/1 coloring.

It may be noted that $p/q\ne x/y$ where $py=qx$. p/q means from p objects we have to select q number of objects which is equal to $\left( {\begin{array}{c}p\\ q\end{array}}\right)$. This may not be same to the number of y objects chosen from x objects which is equal to $\left( {\begin{array}{c}x\\ y\end{array}}\right)$.

Let us consider one interesting graph class known as Kneser fuzzy graph.

Definition 17

The Kneser fuzzy graph is a fuzzy graph whose vertices correspond to the r-element subsets of a set of n elements and two vertices are adjacent if and only if their corresponding sets are distinct. It is denoted by $KG_{n,r}$.

Example 5

Here, we give an example of Kneser fuzzy graph $KG_{4,2}$ (as shown in Fig. 10) on the set of vertices $\{a,b,c,d\}$. Here $n=4$ and $r=2$. So, there are ${4 \atopwithdelims ()2}$ number of vertices and it has 3 edges since there are $\frac{{4 \atopwithdelims ()2}\times {2 \atopwithdelims ()2}}{2}=3$ distinct pair of sets.

Fig. 10

Kneser fuzzy graph with 6 vertices

Note 5

A Kneser graph of n elements has ${n \atopwithdelims ()r}$ number of vertices and $\frac{{n \atopwithdelims ()r}\times {n-r \atopwithdelims ()r}}{2}$ number of edges. The complete fuzzy graph of n vertices is a Kneser graph $KG_{n,1}$.

As like a proper n-coloring of a fuzzy graph is seen as a homomorphism between a fuzzy graph and $KG_{p,q}$, similarly a proper p/q coloring of a fuzzy graph can be seen as a homomorphism from the fuzzy graph $G=(V, \sigma ,\mu )$ and Kneser graph $KG_{p,q}$.

The fuzzy fractional chromatic number is the least of all the rational number p/q such that there exists a proper p/q coloring of G. It may not be clear that the fuzzy fractional chromatic number may be rational number for an arbitrary fuzzy graph. In order to show this, we give another definition of fuzzy fractional coloring.

Definition 18

Let $\ell (G)$ be the set of all independent sets of a fuzzy graph $G=(V, \sigma ,\mu )$. A mapping $f:\ell (G)\rightarrow [0,1]$ is called fuzzy fractional coloring of G if ${{\sum \limits _{v\in S,S\in \ell (G)}}f(S)\ge 1}$, for each $v\in V$. The sum of the functional values over all independent sets is called the weight of the fuzzy fractional coloring. The least possible weight of a fuzzy fractional coloring is called the fuzzy fractional chromatic number of G and it is denoted by $\gamma _F(G)$.

For a fuzzy graph G, fuzzy fractional chromatic number is less than or equal to ordinary fuzzy chromatic number i. e., $\gamma _F(G)\le \gamma (G)$.

Definition 19

A fuzzy fractional coloring in a fuzzy graph $G=(V, \sigma ,\mu )$ is said to be regular if ${{\sum \nolimits _{v\in S,S\in \ell (G)}}f(S)=1}$, for each $v\in V$.

Theorem 2

Fuzzy fractional chromatic number of a fuzzy subgraph H is less than or equal to the fuzzy fractional chromatic number of the fuzzy graph G, i.e. $\gamma _F(H)\le \gamma _F(G)$.

Proof

Let $H=(B,\sigma _1,\mu _1)$ be a fuzzy subgraph of the fuzzy graph $G=(V,\sigma ,\mu )$. $\square$

Case 1

B = V

Since the vertices in H and G are same, therefore the number of strongly adjacent vertices are also same in H and G. Hence, in this case $\gamma _F(H)=\gamma _F(G)$.

Case 2

B $\subset$ V

Since, the number of vertices in H is less than the number of vertices in G, therefore the number of strongly adjacent vertices in H is also less than the number of strongly adjacent vertices in G. Therefore, any proper fuzzy fractional coloring of G, restricted to B, is a proper fuzzy fractional coloring of H. Hence, in this case, $\gamma _F(H)<\gamma _F(G)$.

4.2.1 Method of fuzzy fractional coloring of a fuzzy graph

Here we will discuss the method to find the fuzzy fractional coloring of a fuzzy graph $G=(V, \sigma ,\mu )$.

Step 1 First, find out the strong adjacent vertices of the given fuzzy graph G.

Step 2 Remove all edges between the non strongly adjacent vertices.

Step 3 Next, find out the independent sets in between strongly adjacent vertices. Since the given graph is finite therefore the number of independent sets is also finite.

Step 4 For each independent set, select one color.

Step 5 Allot a fraction to each independent set in such a way that ${{\sum \limits _{v\in S,S\in \ell (G)}}f(S)\ge 1}$.

This step can be performed by solving the following linear programming problem:

$$\begin{aligned} \text {Minimize}\quad&{z=\mathbf {cx}} \\ \text {Subject to}\quad&A\mathbf {x}\ge \mathbf {1} \\ and&~~ {\mathbf {x} > \mathbf {0}~~\; }\\ \end{aligned}$$

where

$\mathbf {x}=[x_1,x_2,\ldots ,x_n]^T$, each $x_j, j=1,2,\ldots n$ represents the weight of the colors,

$\mathbf {1}=[1,1,\ldots ,1]^T=\mathbf {c}^T$,

$\mathbf {0}=[0,0,\ldots ,0]$ and the matrix A can be constructed in the following way

• 1. The rows are indexed by the vertices and columns are indexed by the sets of all independent sets.

• 2. Each row is essentially the characteristic function of the corresponding independent sets, with entries equal to 1 on columns corresponding to the vertices in the independent set, and 0 otherwise.

and z is the fuzzy fractional chromatic number of the fuzzy graph of G.

Step 6 For non-strongly adjacent vertices, assign the same colors assigned to the adjacent vertex.

Note 6

Fuzzy fractional chromatic number of fuzzy graph and crisp fractional chromatic number of the associated underlying graph will be same only when all the edges in the fuzzy graph are strong.

Fig. 11

A fuzzy graph $G_1$

Fig. 12

Fuzzy graph $G_2$ corresponding to the fuzzy graph $G_1$ of Fig. 11

Example 6

To describe the method of fuzzy fractional coloring, we consider a fuzzy graph $G_1$ having 7 vertices as shown in Fig. 11.

Here a and g, b and g, g and d, g and e, all are non-strongly adjacent vertices of G. So, all edges between them are deleted from the fuzzy graph $G_1$. Then the Fig. 11becomes as in Fig. 12.

Here, the independent sets are $S_1=\{a,c,d\}, S_2=\{a,c,e\}, S_3=\{c,d,f\},S_4=\{b,e\},S_5=\{b,f\}$. Assign a color to each independent sets whose weight can be determined by the following linear programming program (LPP).

$$\begin{aligned} \text {Minimize}\quad&{z=x_1+x_2+x_3+x_4+x_5}\\ \text {subject to}&\\&\left[ {\begin{array}{ccccc} 1 &{} 1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 1 &{} 1 &{} 0 \\ 1 &{} 1 &{} 0 &{} 0 &{} 1 \\ 1 &{} 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 1 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 1 &{} 1 \end{array} } \right] \quad \left[ {\begin{array}{ccccc} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} } \right] \ge \left[ {\begin{array}{ccccc} 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array} } \right] \\ and&~~ {x_1,x_2,x_3,x_4,x_5 > 0~~\; } \end{aligned}$$

The solution of the above LPP is $x_1=x_2=x_3=x_4=x_5=\frac{1}{2}$. Therefore, the weight of each color is $\frac{1}{2}$ and the fuzzy fractional chromatic number is $\sum x_j=\frac{5}{2}$. Thus the fuzzy fractional coloring of the graph $G_2$ is shown in Fig.13.

Now, to color the original fuzzy graph $G_1$ of Fig. 11, we consider the edges (a, g), (e, g), (d, g), (b, g). Their strengths are calculated as 0.375, 0.428, 0.333, 0.4 respectively. Among them the minimum strength occurs at (d, g). Therefore, the vertex ‘g’ gets the same color set which occurs in ‘d’. Hence, the fuzzy fractional coloring of the fuzzy graph $G_1$ of Fig. 11is shown in Fig. 14, where the membership values of each colored vertices are given by

$$\begin{aligned} \frac{Total~~ weight}{number ~of~ colors}. \end{aligned}$$

For the vertices a, b, d, e, f, g, each get two colors with weight $\frac{1}{2}$. Therefore, membership value of each vertex is

$$\begin{aligned} \frac{\frac{1}{2}+\frac{1}{2}}{1+1}=\frac{1}{2} \end{aligned}$$

and the vertex c gets three colors each of weight $\frac{1}{2}$. The membership values of c is

$$\begin{aligned} \frac{\frac{1}{2}+\frac{1}{2}+\frac{1}{2}}{1+1+1}=\frac{1}{2} \end{aligned}$$

Fig. 13

Fuzzy fractional coloring the graph $G_2$

Fig. 14

Fractional coloring of the fuzzy graph $G_1$

Theorem 3

For a fuzzy graph G, $\gamma _{F}(G^{0.5})= \chi _{F}(G^*)$.

Proof

Let $G=(V, \sigma ,\mu )$ be a fuzzy graph. Now $G^{0.5}=(V^{0.5},E^{0.5})$, where $V^{0.5}=\{a\in V | I_a\ge 0.5\}$ and $E^{0.5}=\{(a,b)\in E | I_{(a,b)}\ge 0.5\}$. The vertices, which are strongly adjacent to each other in $G^{0.5}$ is also strongly adjacent vertices in G. Therefore, there exists an one to one corresponding between the vertices in $G^{0.5}$ and G. Hence, $\gamma _{F}(G^{0.5})= \chi _{F}(G^*)$. $\square$

4.3 Fuzzy fractional clique

Now, we will investigate the lower bound of fuzzy fractional coloring. For this, we introduce the fuzzy fractional clique below:

Definition 20

Let $\ell (G)$ be the set of all independent sets of a fuzzy graph $G=(V, \sigma ,\mu )$. A mapping $\phi :V(G)\rightarrow [0,\infty ]$ is called fuzzy fractional clique of G if ${{\sum \limits _{v\in S,S\in \ell (G)}}\phi (v)\le 1}$, for each $v\in V$. The sum of the functional values over domain set is called the weight of the fuzzy fractional clique. Fuzzy fractional clique number is the supremum of all possible weights of a fuzzy fractional cliques of fuzzy graph and it is denoted by $\omega _F(G)$.

4.3.1 Equality of fuzzy fractional clique and fuzzy fractional chromatic number

We can say that fuzzy fractional clique is the dual concept of fuzzy fractional coloring. For fuzzy fractional coloring, we have to minimize the weight of the fuzzy fractional coloring. For fuzzy fractional clique, we can construct an LPP as follows:

$$\begin{aligned} \text {Minimize}\quad&{z=\mathbf {cx}} \\ \text {Subject to}\quad&A\mathbf {x}\ge \mathbf {1} \\ and&~~ {\mathbf {x} \geqslant \mathbf {0}~~\; } \end{aligned}$$

where

$\mathbf {x}=[x_1,x_2,\ldots ,x_n]^T$,

$\mathbf {1}=[1,1,\ldots ,1]^T=\mathbf {c}^T$,

$\mathbf {0}=[0,0,\ldots ,0].$

The dual of the above LPP is

$$\begin{aligned} \text {maximize}\quad&{w=\mathbf {v}} \\ \text {subject to}\quad&A^T\mathbf {v}\le \mathbf {c} \\ and&~~ {\mathbf {v} \geqslant \mathbf {0}~~\; } \end{aligned}$$

where

$\mathbf {v}=[v_1,v_2,\ldots ,v_n]^T$,

$\mathbf {1}=[1,1,\ldots ,1]^T=\mathbf {c}^T$,

$\mathbf {0}=[0,0,\ldots ,0]$ and the matrix A can be constructed in the following way

• 1. We first find out the strongly adjacent vertices of the given fuzzy graph $G=(V, \sigma ,\mu )$.

• 2. Next, we find out the independent sets from strongly adjacent vertices. Since the given graph is finite therefore number of independent sets is also finite namely $S_1,S_2,\ldots ,S_n$.

• 3. The columns are indexed by the vertices and rows are indexed by the sets of all independent sets.

• 4. Each row is essentially the characteristic function of the corresponding independent sets, with entries equal to 1 on columns corresponding to the vertices is in the independent set, and 0 otherwise.

Since, fuzzy fractional chromatic number and fuzzy fractional clique number are dual to each other, both of them have same optimal value provided both of them are feasible. Since, any proper coloring is in the feasible region for the primal and the zero vector is in the feasible region for the dual. Hence, by strong duality theorem, we have for a fuzzy graph, $\omega _F(G)=\gamma _F(G)$.

Corollary 1

If H is a fuzzy subgraph of G, then $\omega _F(H)\le \omega _F(G)$.

Proof

Since $\omega _F(G)=\gamma _F(G)$ for any fuzzy graph and $\gamma _F(H)\le \gamma _F(G)$ for any fuzzy graph therefore $\omega _F(H)\le \omega _F(G)$. $\square$

Theorem 4

For any fuzzy graphs G and H, $\gamma _F(G\circ H)=\gamma _F(G)\gamma _F(H)$.

Proof

Let us consider that $\gamma _F(G)=p$ and $\gamma _F(H)=q$. Let c be a fuzzy fractional coloring of value p of the fuzzy graph G and $c'$ be a fuzzy fractional coloring of value q of the fuzzy graph H. Define a function $c''$ for the independent sets of $G\circ H$ as follows:

An independent set A of $G\circ H$ is of the form $A=\{(a,b): a\in ~U and~ b\in V, ~where~ U, ~V are ~the ~independent ~sets~of ~G ~and~ H ~respectively\}$. Let $c''(A)=c(U) c'(V)$, and for any other independent sets B of $G\circ H$, we consider $c''(B)=0$. Then it can be easily verified that $c''$ is a fuzzy fractional coloring of the fuzzy graph $G\circ H$ of value pq. Since fuzzy fractional coloring is the least among all the values therefore $\gamma _F(G\circ H)\le \gamma _F(G)\gamma _F(H)$.

For other part we use the fuzzy fractional clique number. To prove $\gamma _F(G\circ H) \ge \gamma _F(G)\gamma _F(H)$, it is enough to prove that $\omega _F(G\circ H)\ge \omega _F(G)\omega _F(H)$ since for any fuzzy graph G we have $\gamma _F(G)=\omega _F(G)$ by duality theorem. Now by similar argument made in above we can similarly show that $\omega _F(G\circ H)\ge \omega _F(G) \omega _F(H)$ as fuzzy fractional coloring is the supremum among all of its values. $\square$

Remark 1

From the Figs. 6 and 7, we see that lexicographic product is not commutative. From the Theorem 4, it follows that $\gamma _F(G\circ H)=\gamma _F(H\circ G)$.

Theorem 5

For any fuzzy graph G and H, $\gamma (G\circ H)\ge \gamma _F(G)\gamma (H)$.

Proof

Let $\gamma (H)=n$. Then we have

$$\begin{aligned} \gamma (G\circ H)&=\gamma (G\circ K_n)\\&\ge \gamma _F(G\circ K_n)\\&=\gamma _F(G)\gamma _F(K_n)\\&=\gamma _F(G)n\\&=\gamma _F(G)\gamma (H). \end{aligned}$$

$\square$

Theorem 6

For any two fuzzy graphs G and H, $\gamma (G\circ H)\le \gamma (G)\gamma (H)$.

Proof

Let $G=(V_1,\sigma _1, \mu _1)$ and $H=(V_2,\sigma _2, \mu _2)$ be two fuzzy graphs where $\gamma (G)=a$ and $\gamma (H)=b$. Since $\gamma (G)=a$, then there exists an homomorphism f from $V_1$ to $K_a=(V_3, \sigma _3, \mu _3)$, the complete fuzzy graph having $|V_3|=a$ vertices, such that

• 1. $\sigma _1(x)\le \sigma _3(f(x))$, for all $x\in V_1$.

• 2. $\mu _1(x,z) \le \mu _3(f(x),f(z))$, for all $(x,z)\in \widetilde{V_1}^2$.

Similarly, there exists another homomorphism g from $V_2$ to $K_b=(V_4,\sigma _4, \mu _4)$, the complete fuzzy graph having $|V_4|=b$ vertices, such that

• 1. $\sigma _2(y)\le \sigma _4(g(y))$, for all $y\in V_2$.

• 2. $\mu _2(y,w) \le \mu _4(g(y),g(w))$, for all $(y,w)\in \widetilde{V_2}^2$.

An independent set A of $G\circ H$ is of the form A=$\{(x,y): x\in X ~and~ y\in Y$, where X, Y are the independent sets of G and H respectively}. Now, the lexicographic product of G and H is $G\circ H=(V_1\times V_2, \sigma _5, \mu _5)$ is also a fuzzy graph. Again, $K_a\times K_b=(V_6,\mu _6, \sigma _6)$ is a complete fuzzy graph having $|V_6|=ab$ number of vertices. Let there exists a homomorphism $h:V_1\times V_2\rightarrow K_{a}\times K_{b}$, defined by $h(x,y)=(f(x),g(y))$. We are to show that

• 1. $\sigma _5(x,y)\le \sigma _6(h(x,y))$, for all $x\in V_1~and~y\in V_2$.

• 2.

  • (a) $\mu _5\{(x,y),(z,w)\} \le \mu _6\{h(x,z),h(y,z)\}$, for all $(x,z)\in {E_1}$ and $(y,w)\in {E_2}$,

  • (b) $\mu _5\{(x,y),(x,w)\} \le \mu _6\{h(x,z),h(y,z)\}$, for all $x\in {V_1}$ and $(y,w)\in {E_2}$.

Now,

$$\begin{aligned} \sigma _5(x,y)&=min\{\sigma _1(x),\sigma _2(y)\}\\&\le min\{\sigma _3(f(x)),\sigma _4(g(y))\}~~~~~~~~~~~~~(as\,\,f ~and~g ~are~ homomorphism)\\&=\sigma _6(f(x),g(y))\\&=\sigma _6(h(x,y))\\ Hence,~ \sigma _5(x,y)&\le \sigma _6(h(x,y)) ~for ~all~ x\in V_1~and~y\in V_2. \end{aligned}$$

Again,

$$\begin{aligned} \mu _5\{(x,y),(z,w)\}&=\mu _1(x,z)\wedge \mu _2(y,w)\\&\le \mu _3(f(x),f(z))\wedge \mu _4(g(y),g(w))~~~~~~(as \,\,f ~and~ g ~are~ homomorphism)\\&=\mu _6\{(f(x),g(y)),(f(z),g(w))\}\\&=\mu _6\{h(x,y),h(z,w)\}\\ Hence,~ \mu _5\{(x,y),(z,w)\}&\le \mu _6\{h(x,y),h(z,w)\} ~for ~all~ (x,z)\in {E_1} ~and~ (y,w)\in {E_2}, \end{aligned}$$

and

$$\begin{aligned} \mu _5\{(x,y),(x,w)\}&=\sigma _1(x)\wedge \mu _2(y,w)\\&\le \sigma _3(f(x))\wedge \mu _4(g(y),g(w))~~~~~~~(as \,\,f ~and~ g ~are~ homomorphism)\\&=\mu _6\{(f(x),g(y)),(f(x),g(w))\}\\&=\mu _6\{h(x,y),h(x,w)\}\\ Hence,~ \mu _5\{(x,y),(x,w)\}&\le \mu _6\{h(x,y),h(x,w)\} ~for~ all~ x\in {V_1} ~and~ (y,w)\in {E_2}. \end{aligned}$$

Combining all this together, we can say that h is a homomorphism between $V_1\times V_2$ to $K_{a}\times K_{b}$. Since chromatic number is the least among them therefore $\gamma (G\circ H)\le \gamma (G)\gamma (H)$. $\square$

Corollary 2

For any fuzzy graph G, $\gamma (G\circ K_n)=n\gamma (G)$.

Proof

From Theorem 6, $\gamma (G\circ H)\le \gamma (G)\gamma (H)$ for any two fuzzy graphs G, H. Let us consider $H=K_n$. In this case, then $\gamma (H)=n$. Hence $\gamma (G\circ K_n)\le n\gamma (G)$. $\square$

Now, from Theorem 5, $\gamma (G\circ H)\ge \gamma _F(G)\gamma (H)$. Take $H=K_n$, then $\gamma _F(H)=n$. Hence $\gamma (G\circ K_n)\ge n\gamma (G)$. Therefore, $\gamma (G\circ K_n)=n\gamma (G)$.

Theorem 7

Let $G=(V_1,\sigma _1,\mu _1)$ and $H=(V_2,\sigma _2,\mu _2)$ be two fuzzy graphs and P be their disjoint union. Then the following holds:

• (i) $\omega (P)=max\{\omega (G),\omega (H)\}$,

• (ii) $\gamma (P)=max\{\gamma (G), \gamma (H)\}$,

• (iii) $\gamma _F(P)=max\{\gamma _F(G),\gamma _F(H)\}$,

Proof

Here the first and second equalities are trivial.

(iii) Since G and H both are the subgraphs of $G\bigsqcup H$ therefore

$$\begin{aligned} \gamma _F(P)\ge max\{\gamma _F(G),\gamma _F(H)\}. \end{aligned}$$

(1)

To prove the reverse inequality, let $U_G,U_H$ be two fuzzy fractional coloring of G and H respectively. Without loss of generality, let us consider $\gamma _F(G)=max\{\gamma _F(G),\gamma _F(H)\}$. Here each maximal independent set is of the form $I_G\sqcup I_H$ where $I_G$ is a maximal independent set in G and $I_H$ is a maximal independent set in H. Let us consider a fuzzy fractional coloring U of P in

$U_{I_G\sqcup I_H}=U_{I_G} \times \frac{U_{I_H}}{\gamma _F(H)}$.

Then $U_{I_G\sqcup I_H}$ is a proper fuzzy fractional coloring as for any $x \in V_1$,

$$\begin{aligned} \sum _{x \in G}U_{I_G\sqcup I_H}=\sum _{x \in I_G}U_{I_G} \times \sum _{ I_H}\frac{U_{I_H}}{\gamma _F(H)}=\sum _{x \in I_G}U_{I_G}\ge 1 \end{aligned}$$

and for any $y\in V_2$,

$$\begin{aligned} \sum _{y \in H}U_{I_G\sqcup I_H}=\sum _{ I_G}U_{I_G} \times \sum _{ y \in I_H}\frac{U_{I_H}}{\gamma _F(H)}=\gamma _F(G) \times \sum _{y \in I_H}\frac{U_{I_H}}{\gamma _F(H)}\ge \frac{\gamma _F(G)}{\gamma _F(H}\ge 1. \end{aligned}$$

Now, the value is equal to

$$\begin{aligned} \sum _{x \in {I_G\sqcup I_H}}U_{I_G\bigsqcup I_H}=\sum _{x \in I_G}U_{I_G} \times \sum _{ x \in I_H}\frac{U_{I_H}}{\gamma _F(H)}=\sum _{x \in I_G}U_{I_G}=\gamma _F(G). \end{aligned}$$

Therefore

$$\begin{aligned} \gamma _F(P)\le max\{\gamma _F(G),\gamma _F(H)\} \end{aligned}$$

(2)

Hence from (1) and (2), ${\gamma _F(P)=max\{\gamma _F(G),\gamma _F(H)\}}$.

5 An application

In modern day, examination system is an important part of education system to evaluate students performance. In any university, there are some specific courses in PG courses which has to be taken by each and every student during PG courses. Therefore examination scheduling is one of the major issue in any university.

To discuss the above problem, we consider a university in which the following courses are opted:

• 1. Operational research.

• 2. Complex analysis.

• 3. Functional analysis.

• 4. Graph theory.

• 5. Combinatorics.

• 6. Number theory.

• 7. Algebra.

• 8. Coding theory.

• 9. Real analysis.

• 10. Topology.

Each student must opt three courses in the examination. It is presumed that each student will appear for one course in a particular day. In examination schedule, it is expected that total number of days should be minimum to complete the entire examination. The subject combination for this university is given bellow:

• 1. {coding theory, real analysis, topology}.

• 2. {coding theory, operations research, complex analysis}.

• 3. {real analysis, functional analysis, topology}.

• 4. {coding theory, graph theory, combinatorics}.

• 5. {functional analysis, real analysis, complex analysis}.

• 6. {functional analysis, algebra, combinatories}.

• 7. {combinatorics, topology, functional analysis}.

• 8. {operations research, graph theory, algebra}.

• 9. {operations research, graph theory, number theory}.

• 10. {algebra, number theory, coding theory}.

• 11. {coding theory, operations research, real analysis}.

Let A(p) denote the set of students those who opted for the course p.

Let us construct a fuzzy graph. Let S be the set of students and $P = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8,v_9,v_{10}\}$ be the set of courses namely operational research, complex analysis, functional analysis, graph theory, combinatorics, number theory, algebra, coding theory, real analysis and topology respectively. These courses are taken as vertices. Since there are 10 courses, so the fuzzy graph for this problem has 10 vertices. There is an edge between two vertices a, b if $A(a)\cap A(b)\ne \phi$. The membership value of the vertices is given according to the demand of courses among the students. We assume the membership value of some vertices to be ‘1’ if it’s demand is $90\%$ or more among of the total number of students and the membership value to be ‘0’ if it’s demand is less than $5\%$ among the total number of students. The membership values of the edges are determined depending on the teachers’ capability among all the teachers to teach both the courses. Therefore, the corresponding fuzzy graph is shown in Fig. 15.

Fig. 15

Corresponding fuzzy graph for 10 courses

Our main object is to minimize the total number of days to complete the examination. Therefore this problem is modeled as a fuzzy graph coloring problem in which we have to find out the least chromatic number of the fuzzy graph.

The fuzzy graph in Fig. 16 is constructed from the fuzzy graph in Fig. 15 based on strong adjacent vertices.

Fig. 16

Fuzzy graph obtained from Fig. 15 based on strong adjacent vertices

The fuzzy coloring of the fuzzy graph in Fig. 16 is shown in Fig. 17.

Fig. 17

Fuzzy coloring of the fuzzy graph Fig. 16

Since, all the edges of the fuzzy graph of Fig. 16 are strong, therefore fuzzy coloring and ordinarily coloring are same. The chromatic number of fuzzy graph of Fig. 16 is 5. Therefore, total 5 days is required to complete the entire examination system using the fuzzy coloring of the fuzzy graph method.

Now, we calculate fuzzy fractional chromatic number of the fuzzy graph of Fig. 16. First of all we find out the independent sets. The independent sets are $\{v_1,v_3\}, \{v_1,v_5\}, \{v_1,v_{10}\},\{v_2,v_4,v_{10}\}, \{v_2,v_5,v_6\}, \{v_3,v_4\}, \{v_4,v_9\}, \{v_6,v_9\}, \{v_6,v_2,v_{10}\}, \{v_7,v_9,v_5\}, \{v_7,v_2\}, \{v_7,v_{10}\}, \{v_3,v_6\}.$

Fig. 18

Fuzzy fractional coloring of fuzzy graph Fig. 16

Now we assign a color to every independent set with weight $\frac{1}{3}$ for every colors. Since $v_8$ is a non-strongly adjacent vertex therefore it can get any of the color sets of $v_9$ or $v_7$. Hence, the total fuzzy fractional chromatic number of the fuzzy graph of Fig. 15 is $\frac{13}{3}$ which is less than 5 (Fig. 18).

Therefore, only $\frac{13}{3}=4.33>4$ days, which is equivalent to 5 days, is required to complete the entire examination system. The days required to complete the entire examination system is same both in fuzzy coloring and fuzzy fractional coloring method. But if we think it as a chromatic number of the fuzzy graph then the fuzzy fractional chromatic number is less than the fuzzy chromatic number of the fuzzy graph shown of Fig. 15.

6 Conclusions

In this paper, we define k-strong adjacent vertices, fuzzy graph coloring and homomorphism, fuzzy fractional coloring and fuzzy fractional clique, equality of fuzzy fractional chromatic number and fuzzy fractional clique number. Some properties of fuzzy fractional chromatic number and chromatic number of fuzzy graph on lexicographic product and disjoint union of two fuzzy graphs are given. Finally a real life application is also given to show its practicability. One can extend this research work of fuzzy fractional coloring on different types of fuzzy graphs and it’s properties along with real life applications.