Vertex-coloring of fuzzy graphs: A new approach

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.