Colouring of graphs is being used in several representations of real world systems like map colouring, traffic signalling, etc. This study introduces the edge colouring of fuzzy graphs. The chromatic index and the strong chromatic index are defined and related properties are investigated. In addition, job oriented web sites, traffic light problems have been presented and solved using the edge colouring of fuzzy graphs more effectively.

The concept of fuzzy graph, introduced by Kauffman (

Sometimes, the relationship (edges) is more meaningful than the people (nodes). For example, the links in fuzzy social networks are more important than the nodes. Thus, it is essential to show the fuzzy links properly by colouring. Edge colouring, a related term, is important to the problems which are based on uncertainty. In Section

A graph is defined as a pair

A

A

A

The strength of a path is the minimum membership value of an edge in the path. The maximum of all strengths of paths between two vertices is the strength of connectivity between the vertices.

The

A fuzzy graph

A fuzzy graph

Samanta

Let

Hence, the colour

According to the above definition of fuzzy colour, different fuzzy colours are constructed from a basic colour. For example, red is a basic colour. A “fuzzy red” colour may be formed from red by mixing 0.9 units of red colour with 0.1 units of white colour. This “fuzzy red” colour is denoted by

In crisp graph colouring, two edges have different colours if they are adjacent. Otherwise, the colour may be the same. In fuzzy edge colouring, two edges have fuzzy colours whose basic colours are different, if they are adjacent. Otherwise, their fuzzy colours may be the same and from the same basic colour.

Let

The minimum number of basic colours needed to colour a fuzzy graph is called fuzzy chromatic index of a fuzzy graph. Suppose that such minimum number of basic colours is

Formally, the definition of chromatic index for fuzzy graphs is given as follows. The concept of this chromatic index will allow to mention the weight of edge colouring.

Let

The chromatic index on fuzzy graphs is a pair whose first element represents the crisp chromatic index, and the second element is its weight. The crisp number indicates only the number of different colours required to colour the edges of a graph while the weight represents the sum of strengths of the edges. This weight is meaningful only when it is of a very high or very low value, i.e. all edges are strong, or all edges are weak. Thus, the weight needs further restrictions.

An example is considered in Fig.

Edge colouring of fuzzy graphs.

Let

Let

The weight of the chromatic number is significant only if the weight is very large or very small. Suppose that two fuzzy graphs have chromatic indexes which are

Let us consider a fuzzy graph shown in Fig.

Colouring of strong edge of fuzzy graphs.

Let

Again, some of the basic colours are considered strong. However, there exist some basic colours which are not strong, i.e.

Lastly, none of the basic colours is strong. In this case

Let

Let

Let

Hence,

If the fuzzy cycle has an even number of edges, then to colour this cycle, only two basic colours are needed. So,

Hence,

If the fuzzy graph has an odd number of edges, then for this cycle three basic colours are needed. So

Let

Suppose

In case of upper bound, the minimum number of colours required to colour a fuzzy cycle of 3 vertices is

Fuzzy graph colouring problem has various practical applications. One of them is in job oriented web sites. Job oriented web sites are useful in recent years. A lot of recruiters and job seekers gather in these web sites. Fuzzy graphs represent each web site. The following example shows a step by step method of representation of web sites and edge colouring of fuzzy graphs. By looking at the colour of a fuzzy graph, an applicant could understand how many companies suit his/her expertise. Furthermore, on the other side, a company finds a suitable applicant. Thus, the representation of job oriented web sites can be prepared in an easier way using the edge colouring of fuzzy graphs.

Let us assume such a small web site, where

If an applicant’s eligibility suits a company’s demand, it is obvious that there exists a relation between them. Here, the companies and candidates are represented as vertices and their links as edges. Now, the membership values of corresponding vertices of the company may depend on the following issues:

Salary;

Company brand value;

Product value;

Job security;

Medical benefits;

Car benefits;

Insurance benefits;

Accommodation benefits;

Service rule;

Service hours;

Job responsibility.

Academic qualification;

Experience;

Language;

Communication skill;

Age;

Salary requirement;

Compensation;

Behaviour.

The membership values of edges depend on matching the companies’ profiles with the applicants’ profiles. Then, the relationship between companies and applicants is shown as a fuzzy bipartite graph, shown in Fig.

Representation of companies and applicants in a job oriented web site.

Suppose, in particular, 5 companies and 4 applicants are registered on this job oriented web site (see Fig.

For example, in a particular case, the membership values of vertices

When a company or an applicant logins into this web site, then they get a fuzzy subgraph like Fig.

Fuzzy sub graph for the vertex

Fuzzy graph of the job oriented web site.

If these two fuzzy subgraphs are coloured by fuzzy colours, then the applicant

A company (say Infosis) wants to find suitable candidates. Then after login, it gets a fuzzy subgraph (Fig.

From the chromatic index an applicant can realise how many companies are suitable for his/her recruitment and from the weight he/she can understand the chance of recruitment. And from the colour density of the fuzzy graph he understands which company is the best for him. Also, from the strong chromatic index it can be determined how many companies can select him.

Similarly, when a company logins, it gets a coloured fuzzy subgraph shown in Fig.

Fuzzy sub graphs of the fuzzy graph of Fig.

Edge colouring of the fuzzy sub graphs.

CCTV for collection of data.

One of the most useful real life applications of the edge colouring is in traffic light problems. Traffic light system uses three standard colours: red, amber (yellow), green, following the universal colour code. The green light allows traffic to proceed in the denoted direction. The amber (yellow) light warns that more precautions should be taken to cross the road. The red signal prohibits any traffic from proceeding. However, in the present traffic light system, a traveller does not know how much the traffic is congested. This limitation has to be removed here. Traffic light system will be modified by the edge colouring of fuzzy graphs.

It takes every route as a fuzzy vertex. An edge between two vertices is drawn if the routes have a junction. The edge membership values are calculated based on the congestion of routes and the road condition. The data is collected from real time CCTV (see Fig.

Thus a fuzzy graph

Now, a seven point crossing (for example, Park circus seven point crossing, Kolkata, West Bengal, India, see Fig.

Seven point crossing park circus, Kolkata (collected from Google Map).

Fuzzy graph of seven point crossing.

Fuzzy subgraph of Fig.

Edge colouring of fuzzy graph.

Let us consider at a particular time the membership value of the edges PA, PB, PC, PD, PE, PF be

When a traveller is travelling the P road, it would be helpful, if all the information about the next crossing was displayed in two or three display boards before the crossing. From the chromatic index the traveller can understand how many roads are open at the time of crossing, and from the weight, the total traffic condition. For this purpose, the congestion of the next crossing is to be represented in terms of percentage. Here,

Red signal with percentage of mixing of colours.

Also we can use this depth of colour in red (

The stopping time can be fixed with the help of the membership value of the red signal. If the membership value of the red colour is increased, then the stopping time will decrease.

In this study, a concept of edge colouring has been introduced. A related term, chromatic index, is also defined in a different way. A weight is associated with each of the chromatic indexes. This weight might be defined in different ways. But the proposed method mentions the depth of the colours to be used to colour a graph. At the end of this paper, the traffic light problem is updated. In that problem, if the subgraph is uploaded for online traffic condition, then the input graph will be compatible with Google Traffic indicating system. It is seen that Google Traffic system calculates the data from the flow of mobiles. But here, membership values are calculated from real-time CCTV. Google Traffic uses three or four colours to represent the condition of the traffic, but the proposed method uses the colour density with a percentage, which is much more helpful to the traveller. Thus, a user can easily understand the present condition of the traffic. There are many real field problems which can be solved using this technique of colouring, such as transportation problems, social networking problems, sport modelling. The proposed method may be implemented empirically in the existing traffic light systems. The theoretical approach of edge colouring will be beneficial to other graph colouring problems as well. In future studies, more uncertainty may be represented through generalized fuzzy graphs.