Affiliations: Department of Mathematics, Sirjan Branch, Islamic Azad University, Sirjan, Iran
Correspondence:
[*]
Corresponding author. Esmail Keshavarz, Department of Mathematics, Sirjan Branch, Islamic Azad University, Sirjan, Iran. Tel.: +98 034 41523427; Fax: +98 034 41523001; E-mails: ekeshavarz@iausirjan.ac.ir; esmailk212@gmail.com.
Abstract: In this paper, a new vertex-coloring problem of a fuzzy graph with crisp vertices and fuzzy edges is studied. Membership degree of a fuzzy edge is interpreted as incompatibility degree of its associated incident vertices. This interpretation can be used to define the concept of total incompatibility. Here, unlike the traditional graph coloring problems, two adjacent vertices can receive same colors; these type of vertices and their associated edge are named incompatible vertices and incompatible edge, respectively. In proposed coloring methodology, the total incompatibility of a vertex-coloring is defined as the sum of incompatibility degrees of all incompatible edges. Then, based on the minimum possible degree of total incompatibilities, fuzzy chromatic number of a fuzzy graph is introduced. In order to find an optimal k-coloring, with minimum degree of total incompatibly, firstly a binary programming problem is formulated. Then, a hybrid local search genetic algorithm is designed to solve the large-size problems. Practical uses of the proposed algorithm are illustrated and analyzed by different-size problems. Finally, a cell site assignment problem, as a real world application of the presented fuzzy graph vertex-coloring, is formulated and solved.
