## 1 Introduction

*et al.*(2016a), Sarkar and Samanta (2017), Mahapatra

*et al.*(2019a). Early in the literature, one of the useful problems, the traffic light problem, was solved using the crisp graph colouring technique. But, in traffic light problems, some routes are busier compared to the other routes. Also, sometimes, two routes are open simultaneously with some caution. Here “busy”, “caution” are fuzzy terms. So fuzzy/uncertainty could be included in the traffic light problem. Munoz

*et al.*(2005) designed the traffic light problem by fuzzy graphs and introduced the method of colouring in fuzzy graphs. The edge colouring of fuzzy graphs could demonstrate the traffic light problem properly. The membership value of edges is calculated from the congestion of the route and the probability of accidents. If the signal lights are based on these membership values and used alongside the fuzzy colour, the density of the signal colours could indicate the flow of traffic in a particular region. In that paper, the fuzzy graphs were considered with crisp vertices and fuzzy edges. Then

*α*-cuts Mordeson and Nair (2000) of these fuzzy graphs were coloured according to the method of the crisp graph colouring. Thus, for different values of

*α*, there are different crisp graphs, and these crisp graphs are coloured. Therefore, the chromatic index varies for the same fuzzy graphs for different values of

*α*. Also, Bershtein and Bozhenuk (2001) proposed a different technique to colour fuzzy graphs. In this paper, a term separation degree of fuzzy graphs has been defined and based on the value of separation degree, the number of minimum colour is found. Vertex colouring on fuzzy graphs is applied for map colouring Samanta

*et al.*(2016b). Recently, major developments on chromatic index on fuzzy graphs are obtained from the papers of Rosyida

*et al.*(2016, 2015) and Chen

*et al.*(2017). Kishore and Sunitha Kishore and Sunitha (2014, 2016) introduced chromaticity and strong chromaticity of fuzzy graphs. Mahapatra

*et al.*(2019b) advanced the colouring concept to radio fuzzy graphs and resolved radio frequency problems.

## 2 Preliminaries

*V*is the set, and

*E*is a relation on

*V*. The elements of

*V*are called vertices, and the elements of

*E*are called edges of ${G^{\ast }}$.

*fuzzy set A*on a universal set

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

*fuzzy graph*Rosenfeld (1975) $\xi =(V,\sigma ,\mu )$ is a non-empty set

*V*together with a pair of functions $\sigma :V\to [0,1]$ and $\mu :V\times V\to [0,1]$, such that for all $x,y\in V$, $[\mu (x,y)\leqslant \min \{\sigma (x),\sigma (y)\}]$, where $\sigma (x)$ and $\mu (x,y)$ represent the membership values of the vertex

*x*and of the edge $(x,y)$ in

*ξ*, respectively.

*path*in a fuzzy graph is a sequence of distinct nodes ${x_{0}},{x_{1}},\dots ,{x_{n}}$, such that $\mu ({x_{i-1}},{x_{i}})>0,1\leqslant i\leqslant n$. The fuzzy path is said to be

*fuzzy cycle*if ${x_{0}}$ and ${x_{n}}$ coincide.

*underlying crisp graph*of the fuzzy graph $\xi =(V,\sigma ,\mu )$ is denoted as $\xi =(V,\sigma ,{\mu ^{)}}$ where $\sigma =\{u\in V|\sigma (u)>0\}$ and $\mu =\{(u,v)\in V\times V|\mu (u,v)>0\}$. Thus, for underlying fuzzy graph, $\sigma =V$ is true.

*u*and

*v*.

*bipartite*if the vertex set

*V*can be partitioned into two nonempty sets ${V_{1}}$ and ${V_{2}}$, such that $\mu ({v_{1}},{v_{2}})=0$ if ${v_{1}},{v_{2}}\in {V_{1}}$ or ${v_{1}},{v_{2}}\in {V_{2}}$. Furthermore, if $\mu ({v_{1}},{v_{2}})=\min \{\sigma ({v_{1}}),\sigma ({v_{2}})\}$ for all ${v_{1}}\in {V_{1}}$ and ${v_{2}}\in {V_{2}}$, then

*ξ*is called a fuzzy complete bipartite graph.

## 3 Edge Colouring of Fuzzy Graphs

*et al.*(2016b) defined fuzzy colours as mixed colours. But when a colour is mixed with white, its intensity is reduced. Now, intensity is a fuzzy term. Suppose

*β*$(\leqslant 1)$ units of the colour ${c_{k}}$ are mixed with $1-\beta $ units of white colour, then the mixture is called a standard mixture of the colour ${c_{k}}$. The resulted colour is called the fuzzy colour of the colour ${c_{k}}$ with membership value

*β*, whereas ${c_{k}}$ is called the basic colour. For example, red, black, green, etc. are basic colours. The definition of fuzzy colour is given as follows.

##### Definition 1.

### 3.1 Procedure of Edge Colouring of Fuzzy Graphs

*u*and

*v*, respectively. Also, $\mu (u,v)$ is the membership value of the edge ${e_{j}}$, i.e. $(u,v)$ in the fuzzy graph

*ξ*.

### 3.2 Algorithm to Colour the Edges of a Fuzzy Graph

**Input:**A fuzzy graph $\xi =(V,\sigma ,\mu )$, $|V|=n$. Assume that the vertices are labelled as $1,2,\dots ,n$.

**Output:**Complete a edge coloured graph.

**Step 1:**Calculate ${f_{{e_{j}}}}({c_{i}})=\frac{\mu (u,v)}{\sigma (u)\wedge \sigma (v)}$ of all edges. Also, vertices are to be labelled as $1,2,\dots ,n$.

**Step 2:**First of all, the vertex “1” is focused to colour all its incident edges in such a way that no two incident edges are of the same colours. Here, depths of the colours depend on the $f-$ values which are calculated in Step 1.

**Step 3:**Proceed to direct neighbours of “1” except the previous one which is already focused and label them $11,12,\dots ,1m$, if there are

*m*-such neighbours. Start with the vertex 11 and repeat Step 2 and so on for $12,13,\dots ,1m$.

**Step 4:**Repeat Step 3 until all edges of the graph have been coloured.

## 4 Chromatic Index of Fuzzy Graphs

*N*. Now, this crisp chromatic index is not sufficient to mention the strengths of edges (i.e. the relationship among vertices). For example, chromatic indexes of two fuzzy graphs are the same. Then it is inconclusive when these graphs are being compared. Hence, the chromatic index is associated with some weight. The weight is denoted by

*W*, and defined by $W={\textstyle\sum _{i=1}^{N}}\{{\max _{j}}{f_{{e_{j}}}}({c_{i}})\}$. Where the basic colour ${c_{i}}$ is used to colour the edge ${e_{j}}$ for some

*j*, and depth of colour is ${f_{{e_{j}}}}({c_{i}})$. Thus,

*W*is the sum of the maximum membership values of each basic colour. Now, the chromatic index of a fuzzy graph is denoted by $(N,W)$, where

*N*is the minimum number of basic colours to colour a graph, and

*W*is its weight. It is obvious that the weight of the chromatic index is to be determined by decision makers for a particular case.

### 4.1 Algorithm of Minimum Colouring of Edges of a Fuzzy Graph

**Input:**A fuzzy graph $\xi =(V,\sigma ,\mu )$, $|V|=n$. Assume that the vertices are labelled as $1,2,\dots ,n$.

**Output:**Complete a edge coloured graph.

**Step 1:**Now,

*f*-value (${f_{{e_{j}}}}({c_{i}})=\frac{\mu (u,v)}{\sigma (u)\wedge \sigma (v)}$) of all edges are to be calculated.

**Step 2:**First of all, the vertex “1” is targeted to colour all its incident edges in such a way that the minimum number of colours would be used. Hence, if one colour is used, a different colour is to be used only if the edges are incident to the vertex.

**Step 3:**Proceed to direct neighbours of “1” except the previous one which is already focused and label them $11,12,\dots ,1m$, if there are

*m*-such neighbours. Start with the vertex 11 and repeat Step 2 and so on for $12,13,\dots ,1m$.

**Step 4:**Repeat Step 3 until all edges of the graph have been coloured.

##### Definition 2.

*G*where

*N*is the minimum number of colour needed to colour the graph

*G*and $W={\textstyle\sum _{i=1}^{N}}\{ma{x_{j}}{f_{{e_{j}}}}({c_{i}})\}$, the basic colour ${c_{i}}$ is used to colour the edge ${e_{j}}$ for some

*j*, and the depth of colour is ${f_{{e_{j}}}}({c_{i}})$.

##### Example 1.

##### Proof.

*N*basic colour is required. Here, the membership value of each basic colour is 1. Then the weight of the chromatic index is $\{1+1+1+\cdots N\hspace{2.5pt}\text{times}\}=N$. So, the chromatic index of a complete graph is $(N,N)$. □

##### Proof.

*W*is always positive, i.e. $W>0$. Also, $\mu (x,y)\leqslant \sigma (x)\wedge \sigma (y)$. Thus, $\frac{\mu (x,y)}{\sigma (x)\wedge \sigma (y)}$ ⩽ 1. So, the membership value of each colour is smaller or equal to 1. Now

*W*is the sum of membership values of

*N*basic colours. Hence, $W\leqslant N$, i.e. $0<W\leqslant N$. □

## 5 Strong Chromatic Index of Edge Colouring of Fuzzy Graphs

*ξ*and ${W_{s}}$ is the sum of the membership values of each basic colour. It is assumed that the maximum membership value is taken for the repeated, basic colours.

##### Example 2.

##### Theorem 1.

*Let ξ be a fuzzy graph, and the chromatic index of this fuzzy graph is*$(N,W)$

*, and strong chromatic index is*$({M_{s}},{W_{s}})$

*, then*$N\geqslant {M_{s}}$

*and*$W\geqslant {W_{s}}$

*.*

##### Proof.

*W*is the sum of the maximum membership value of each basic colour, and ${W_{s}}$ is the sum of all the maximum membership values of all strong basic colours. So, in this case, $W>{W_{s}}$.

##### Lemma 3.

*Let ξ be a fuzzy graph with a strong chromatic index*$({M_{s}},{W_{s}})$

*. Then*$2{W_{s}}-M$

*is either zero or positive.*

##### Proof.

*ξ*is coloured by ${M_{s}}$ number of strong basic colours and the membership value of each of the strong basic colours is $\frac{\mu (x,y)}{\sigma (x)\wedge \sigma (y)}$ ($\geqslant 0.5$). Note that ${W_{s}}$ is the sum of membership values of each basic colour. It is assumed that the maximum membership value is taken for repeated basic colours. So, it is true that ${W_{s}}\geqslant 0.5\times {M_{s}}$, where ${M_{s}}$ is the number of basic colours. Hence, $2{W_{s}}-{M_{s}}\geqslant 0$. Then $2{W_{s}}-M$ is either zero or positive. □

##### Theorem 2.

*Let ξ be a fuzzy graph with a strong chromatic index*$({M_{s}},{W_{s}})$

*. Then*$\frac{{M_{s}}}{2}\leqslant {W_{s}}\leqslant {M_{s}}$

*is true.*

##### Proof.

*ξ*be $({M_{s}},{W_{s}})$. The fuzzy graph

*ξ*coloured by ${M_{s}}$ number of strong basic colours and the membership values of all such strong basic colours are $\frac{\mu (x,y)}{\sigma (x)\wedge \sigma (y)}$ $(\geqslant 0.5)$. So, the minimum membership value of the strong colours is 0.5. If all of these ${M_{s}}$ strong basic colours have the minimum membership value, then ${W_{s}}=\{0.5+0.5+\dots {M_{s}}\langle \hspace{2.5pt}\text{times}\}=\frac{{M_{s}}}{2}$. So, the minimum value of the strong weight is $\frac{{M_{s}}}{2}$, i.e. $\frac{{M_{s}}}{2}\leqslant {W_{s}}$. Also, the maximum depth of colour is 1. Now, if each of all of these ${M_{s}}$ number of basic colours has the maximum depth, then ${W_{s}}=\{1+1+1+\dots M\hspace{2.5pt}\text{times}\}={M_{s}}$. So, the maximum value of the strong weight is ${M_{s}}$. Thus, ${W_{s}}\leqslant {M_{s}}$. So, $\frac{{M_{s}}}{2}\leqslant {W_{s}}\leqslant {M_{s}}$ is true. □

##### Lemma 4.

*Let ξ be a fuzzy graph other than complete fuzzy graphs with a chromatic index*$(N,W)$

*and a strong chromatic index*$({M_{s}},{W_{s}})$

*. Then*$\frac{W-{W_{s}}}{N-{M_{s}}}\leqslant 0.5$

*.*

##### Proof.

*ξ*be a fuzzy graph other than complete fuzzy graphs with a chromatic index $(N,W)$ and a strong chromatic index $({M_{s}},{W_{s}})$. So, $N\ne {M_{s}}$, i.e. $(N-{M_{s}})\geqslant 0$. Also, $(N-{M_{s}})$ is the number of coloured edges whose membership value is less than 0.5. And $(W-{W_{s}})$ is the weight of the $(N-{M_{s}})$ edges. Thus, $W-{W_{s}}$ = sum of membership values of $(N-{M_{s}})$ edges. So, $W-{W_{s}}\leqslant 0.5\times (N-{M_{s}})$.

##### Lemma 5.

*Let ξ be a fuzzy cycle with a chromatic index*$(N,W)$

*. If the fuzzy cycle has an even number of edges, then*$N=2$

*and*$0<W\leqslant 2$

*. If the fuzzy cycle has an odd number of edges, then*$N=3$

*,*$0<W\leqslant 3$

*.*

##### Proof.

*W*is $0<W\leqslant N$.

##### Note 1.

*ξ*be a bipartite fuzzy graph and Δ be the maximum degree of this fuzzy graph, then its chromatic index is $(\Delta ,W)$.

##### Theorem 3.

*Let ξ be a fuzzy graph with vertex membership values*1

*and*$({M_{s}},{W_{s}})$

*be its strong chromatic index. Then,*${M_{s}}$

*lies between*$[\frac{1}{2}{\Delta ^{\prime }}(\xi )]$

*and*$[{\Delta ^{\prime }}(\xi )+1]$

*.*(${\Delta ^{\prime }}(x)=\max {\textstyle\sum _{y\in V,\mu (x,y)>0.5}}\mu (x,y)$

*and*$[x]$

*represents greatest integer function*)

*.*

##### Proof.

*ξ*is a fuzzy graph with vertex membership values 1 and $({M_{s}},{W_{s}})$ is its strong chromatic index. If

*ξ*has a vertex

*u*such that $d(u)={\textstyle\sum _{y\in V,\mu (u,y)>0.5}}\mu (u,y)$. Also, the vertex membership values are 1, thus strong edges refer to the edges with membership values more than 0.5. As the chromatic index of the graph is $({M_{s}},{W_{s}})$, $d\leqslant {W_{s}}$ and the number of strong edges incident to

*u*must be smaller than or equal to ${M_{s}}$. Again, ${\Delta ^{\prime }}(x)={\max _{x\in V}}d(x)$. Thus, it is natural $N\geqslant [\frac{1}{2}{\Delta ^{\prime }}(\xi )]$.

*n*. The chromatic index for such cycle is $(n+1,W)$. Thus, the maximum value for chromatic index of such cycles is given as $(N,W)$ where $N=[{\Delta ^{\prime }}(x)+1]$. If edge membership values are maximum, then the chromatic index must have its maximum value $([{\Delta ^{\prime }}(x)+1],[{\Delta ^{\prime }}(x)+1])$. For other graphs, according to Vizing’s theorem, it is well known that the crisp graphs have its maximum chromatic index as ${\Delta ^{\prime }}(x)+1$. Hence, the result for fuzzy graphs that

*N*lies between $[\frac{1}{2}{\Delta ^{\prime }}(\xi )]$ and $[{\Delta ^{\prime }}(\xi )+1]$ is true. □

## 6 Representation of Job Oriented Web Sites by Edge Colouring of Fuzzy Graphs

*N*number of candidates are registered for jobs with their Bio-Data, and

*M*number of companies (recruiters) have registered a certain number of vacancies and the brand value of the company for appropriate candidates (see Fig. 3).

##### Fig. 6

## 7 Representation of Traffic Light Problem

##### Fig. 11

*f*-value, i.e. 0.81 indicates that the congestion is $81\% $. Displaying percentage is helpful in order to understand the congestion of a target road. So with the help of the colouring of the fuzzy subgraph, the traveller would get an idea before crossing about the present condition of the target road. With the help of the chromatic index, the traveller also understands the situation of the target road, i.e. whether the road will open or close.