# Fuzzy Chromatic Polynomial of Fuzzy Graphs with Crisp and Fuzzy Vertices Usingα-Cuts

Authors: Mamo Abebe Ashebo; V. N. Srinivasa Rao Repalle
Journal: Advances in Fuzzy Systems
 (2019)

---

## Abstract

Coloring of fuzzy graphs has many real life applications in combinatorial optimization problems like traffic light system, exam scheduling, register allocation, etc. In this paper, the concept of fuzzy chromatic polynomial of fuzzy graph is introduced and defined based onα-cuts of fuzzy graph. Two different types of fuzziness to fuzzy graph are considered in the paper. The first type was fuzzy graph with crisp vertex set and fuzzy edge set and the second type was fuzzy graph with fuzzy vertex set and fuzzy edge set. Depending on this, the fuzzy chromatic polynomials for some fuzzy graphs are discussed. Some interesting remarks on fuzzy chromatic polynomial of fuzzy graphs have been derived. Further, some results related to the concept are proved. Lastly, fuzzy chromatic polynomials for complete fuzzy graphs and fuzzy cycles are studied and some results are obtained.


---

## Body

## 1. Introduction

Nowadays, many real world problems cannot be properly modeled by a crisp graph theory, since the problems contain uncertain information. The fuzzy set theory, anticipated by Zadeh [1], is used to handle the phenomena of uncertainty in real life situation. A lot of works have been done in fuzzy shortest path problems using type 1 fuzzy set in [2–5]. Dey et al. [6] introduced interval type 2 fuzzy set in the fuzzy shortest path problems. Recently, in [7], the authors proposed a genetic algorithm for solving fuzzy shortest path problem with interval type 2 fuzzy arc lengths. Some researchers also used the fuzzy set theory to touch the uncertainty in crisp graphs. Kaufmann [8] proposed the first definition of fuzzy graph in 1973, based on Zadeh’s fuzzy relations. Later, Rosenfeld [9] introduced another elaborated definition of fuzzy graph with fuzzy vertex set and fuzzy edge set in 1975. He developed the theory of fuzzy graph. After that, Bhattacharya [10] has established some connectivity concepts regarding fuzzy cut nodes and fuzzy bridges. Bhutani [11] has studied automorphisms on fuzzy graphs and certain properties of complete fuzzy graphs. Also, Mordeson and Nair [12] introduced cycles and cocycles of fuzzy graphs. Several authors including Sunitha and Vijayakumar [13, 14], Bhutani and Rosenfeld [15], Mathew and Sunitha [16], Akram [17], and Akram and Dudek [18] have introduced numerous concepts in fuzzy graphs. Fuzzy graph theory has several applications in various fields like clustering analysis, database theory, network analysis, information theory, etc. [19].Coloring of fuzzy graphs plays a vital role in theory and practical applications. It is mainly studied in combinatorial optimization problems like traffic light control, exam scheduling, register allocation, etc. [20]. Fuzzy coloring of a fuzzy graph was defined by authors Eslahchi and Onagh in 2004 and later developed by them as fuzzy vertex coloring [21] in 2006. Another approach of coloring of fuzzy graphs was introduced by Munoz et al. [22]. The authors have defined the chromatic number of a fuzzy graph. Incorporating the above two approaches of coloring of fuzzy graph, Kishore and Sunitha [23] introduced chromatic number of fuzzy graphs and developed algorithm. Dey and Pal [24] introduced the vertex coloring of a fuzzy graph using α-cuts. In [25], they have used the vertex coloring of fuzzy graph to classify the accidental zone of a traffic control. Further, in [26], the authors proposed genetic algorithm to find the robust solutions for fuzzy robust coloring problem. The authors, Ananthanarayanan and Lavanya [20], introduced fuzzy chromatic number and fuzzy total chromatic number of a fuzzy graph using α-cuts. Rosyida et al. [27] proposed a new approach to determine fuzzy chromatic number of fuzzy graph through its δ-chromatic number. Samanta et al. [28] also introduced a new concept for coloring of fuzzy graphs using fuzzy color. Lately, Dey et al. [29] introduced the concept of vertex and edge coloring of vague graphs which are the generalized structure of fuzzy graphs.In the literature, to the best of our knowledge, there is no study on the fuzzy chromatic polynomial of fuzzy graphs. Therefore, in this paper, we consider the chromatic polynomial in fuzzy graph, called fuzzy chromatic polynomial of fuzzy graph. Based on this, we define the concept of fuzzy chromatic polynomial of a fuzzy graph usingα-cuts of fuzzy graph. Also, we determine the fuzzy chromatic polynomial for fuzzy graphs with crisp and fuzzy vertex set. To determine the fuzzy chromatic polynomial, the classical method for computing the chromatic polynomial of crisp graph is used. Next, we derive some interesting remarks on fuzzy chromatic polynomial of fuzzy graph with crisp and fuzzy vertices. Further, we prove more elegant results on fuzzy chromatic polynomial of fuzzy graphs. Finally, we study a fuzzy chromatic polynomial for complete fuzzy graphs and fuzzy cycles.The rest of paper is organized as follows. In Section2, some basic definitions and elementary concepts of fuzzy set, fuzzy graph, and coloring of fuzzy graphs are reviewed. In Section 3, fuzzy chromatic polynomial of a fuzzy graph using α-cut of fuzzy graph is defined. Also, fuzzy chromatic polynomials for fuzzy graphs with crisp and fuzzy vertices are determined. In Section 4, more results on fuzzy chromatic polynomials are proved. Furthermore, fuzzy chromatic polynomial for complete fuzzy graphs and fuzzy cycles are studied. Finally, the paper is concluded in Section 5.


## 2. Preliminaries

In this section, some basic aspects that are necessary for this paper are included. These preliminaries are given in three subsections.


### 2.1. Basic Definitions and Concepts on Vertex Coloring and Chromatic Polynomial

In this subsection some basic definitions and concepts of vertex coloring and chromatic polynomials are reviewed [30, 31].Definition 1.
LetG=(V,E) be a graph. A vertex-coloring of G is an assignment of a color to each of the vertices of G in such a way that adjacent vertices are assigned different colors. If the colors are chosen from a set of k colors, then the vertex-coloring is called a k-vertex-coloring,abbreviated to k-coloring, whether or not all k colors are used.Definition 2.
IfG has a k-coloring, then G is said to be k-colorable.Definition 3.
The smallestk, such that G is k-colorable, is called the chromatic number of G, denoted by χ(G).Definition 4.
LetG be a simple graph. The chromatic polynomial of G is the number of ways we can achieve a proper coloring on the vertices of G with the given k colors and it is denoted by P(G,k). It is a monic polynomial in k with integer coefficients, whose degree is the number of vertices of G.If we are given an arbitrary simple graph, it is usually difficult to obtain its chromatic polynomial by examining the structure of a graph (by inspection). The following theorem gives us a systematic method for obtaining the chromatic polynomial of a simple graph in terms of the chromatic polynomial of null graphs.Theorem 5.
LetG be a simple graph, and let G-e and G/e be the graphs obtained from G by deleting and contracting an edge e. Then(1)PG,k=PG-e,k-PG/e,k


### 2.2. Basic Definitions on Fuzzy Set and Fuzzy Graphs

In this subsection, some basic definitions on fuzzy set and fuzzy graphs are reviewed [1, 9, 19, 32].Definition 6.
A fuzzy setA defined on a nonempty set X is the familyA=x,μAx∣x∈X, where μA:X→I is the membership function. In classical fuzzy set theory the setIis usually defined as the interval [0,1] such that(2)μAx=1,x∈A0,x∉AIt takes any intermediate value between 0 and 1 represents the degree in which x∈A. The set I could be discrete set of the form I={0,1,…,k} where μA(x)<μA(x′) indicates that the degree of membership ofx toA is lower than the degree of membership of x′.Definition 7.
α-cut set of fuzzy set A is defined as Aα is made up of members whose membership is not less than α, Aα=x∈X∣μA(x)≥α. α-cut set of fuzzy set is crisp set.Definition 8.
A fuzzy graphG=(V,σ,μ) is an algebraic structure of nonempty set V together with a pair of functions σ:V→[0,1] and μ:V×V→[0,1] such that for all u,v∈V, μ(u,v)≤σ(u)∧σ(v) and μ is a symmetric fuzzy relation on σ. Here σ(u) and μ(u,v) represent the membership values of the vertex u and of the edge (u,v) in G, respectively.In this paper, we denoteu∧v=min⁡{u,v} and u∨v=max⁡{u,v}. Here, we considered fuzzy graph G is simple (with no loops and parallel edges), finite, and undirected. μ is reflective (that is, μv,v=σv, for all v∈V) and symmetric (that is, μu,v=μv,u, for all (u,v)∈E).Note that a fuzzy graph is a generalization of crisp graph in whichσ(v)=1 for all v∈V and μu,v=1 if u,v∈E and μu,v=0 if u,v∉E. So, all the crisp graphs are fuzzy graphs but all fuzzy graphs are not crisp graphs.Definition 9.
The fuzzy graphG′=(V,σ′,μ′) is called a fuzzy subgraph ofGif for each two elements u,v∈V, we have σ′(u)≤σ(u) and μ′(u,v)≤μ(u,v).Definition 10.
The fuzzy graphG=(V,σ,μ) is called connected if, for every two elements u,v∈V, there exists a sequence of elements u0,u1,…,um such that u0=u, um=v, and μ(ui,ui+1)>0, (0≤i≤m-1).Definition 11.
For any fuzzy graphG=(V,σ,μ), let L={σ(u)>0∣u∈V}∪{μ(u,v)>0∣u≠v,u,v∈V} with k elements. Now assume L={α1,α2,…,αk} such that α1<α2<⋯<αk. The sequence {α1,α2,…,αk} and the set L are called the fundamental sequence and the fundamental set (or level set) of G, respectively.Definition 12.
The underlying crisp graphG∗=(V∗,E∗) of a fuzzy graph G=(V,σ,μ) is such that V∗=u∈V∣σ(u)>0 and E∗=u,v∣μ(u,v)>0.Definition 13.
Forα∈0,1, α-cut graph of a fuzzy graph G=(V,σ,μ) is a crisp graph Gα=(Vα,Eα) such that Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. It is obvious that a fuzzy graph will have a finite number of different α-cuts.


### 2.3. Basic Definitions in Fuzzy Coloring of Fuzzy Graphs

The concept of chromatic number of fuzzy graph was introduced by Munoz et al. [22]. The authors considered fuzzy graphs with crisp vertex set, that is, fuzzy graphs, for which σ(v)=1 for all v∈V and edges with membership degree in [0,1].Definition 14 (see [22]).
IfG=(V,μ) is such a fuzzy graph where V={1,2,3...n} and μ is a fuzzy number on the set of all subsets of V×V, assume I=A∪{0}, where A={α1<α2<…<αk} is the fundamental set (level set) of G. For each α∈I, Gα denote the crisp graph Gα=(V,Eα), where Eα=ij1≤i<j≤n,μ(i,j)≥α} and χα=χ(Gα) denote the chromatic number of crisp graph Gα.By this definition the chromatic number of fuzzy graphs G is the fuzzy numberχ(G)={(i,v(i))/i∈X}, where vi=max⁡α∈I∣i∈Aα and Aα={1,2,3…,χα}.Later Eslahchi and Onagh [21] introduced fuzzy vertex coloring of fuzzy graph. They defined fuzzy chromatic number as the least value of k for which the fuzzy graph G has k-fuzzy coloring as follows.Definition 15 (see [21]).
A familyΓ={γ1,γ2,…,γk} of fuzzy sets on a set V is called a k-fuzzy coloring of G=(V,σ,μ) if(i)
∨Γ=σ,(ii)
γi∧γj=0,(iii)
for every strong edge(x,y) (i.e., μ(x,y)>0 ) of G, min⁡{γi(x),γi(y)}=0 (1≤i≤k).Definition 16 (see [21]).
The minimum numberk for which there exists a k-fuzzy coloring is called the fuzzy chromatic number of G, denoted as χfG.Incorporating the features of the above two definitions, Kishore and Sunitha [23] modified the chromatic number χ(G) of fuzzy graph as follows.Definition 17 (see [23]).
For eachαϵI, Gα denote the crisp graph Gα=(σα,μα) and χα=χ(Gα) denote the chromatic number of crisp graph Gα. The chromatic number of fuzzy graph G=(V,σ,μ) is the number χG=max⁡{χGα∣α∈A}.


## 2.1. Basic Definitions and Concepts on Vertex Coloring and Chromatic Polynomial

In this subsection some basic definitions and concepts of vertex coloring and chromatic polynomials are reviewed [30, 31].Definition 1.
LetG=(V,E) be a graph. A vertex-coloring of G is an assignment of a color to each of the vertices of G in such a way that adjacent vertices are assigned different colors. If the colors are chosen from a set of k colors, then the vertex-coloring is called a k-vertex-coloring,abbreviated to k-coloring, whether or not all k colors are used.Definition 2.
IfG has a k-coloring, then G is said to be k-colorable.Definition 3.
The smallestk, such that G is k-colorable, is called the chromatic number of G, denoted by χ(G).Definition 4.
LetG be a simple graph. The chromatic polynomial of G is the number of ways we can achieve a proper coloring on the vertices of G with the given k colors and it is denoted by P(G,k). It is a monic polynomial in k with integer coefficients, whose degree is the number of vertices of G.If we are given an arbitrary simple graph, it is usually difficult to obtain its chromatic polynomial by examining the structure of a graph (by inspection). The following theorem gives us a systematic method for obtaining the chromatic polynomial of a simple graph in terms of the chromatic polynomial of null graphs.Theorem 5.
LetG be a simple graph, and let G-e and G/e be the graphs obtained from G by deleting and contracting an edge e. Then(1)PG,k=PG-e,k-PG/e,k


## 2.2. Basic Definitions on Fuzzy Set and Fuzzy Graphs

In this subsection, some basic definitions on fuzzy set and fuzzy graphs are reviewed [1, 9, 19, 32].Definition 6.
A fuzzy setA defined on a nonempty set X is the familyA=x,μAx∣x∈X, where μA:X→I is the membership function. In classical fuzzy set theory the setIis usually defined as the interval [0,1] such that(2)μAx=1,x∈A0,x∉AIt takes any intermediate value between 0 and 1 represents the degree in which x∈A. The set I could be discrete set of the form I={0,1,…,k} where μA(x)<μA(x′) indicates that the degree of membership ofx toA is lower than the degree of membership of x′.Definition 7.
α-cut set of fuzzy set A is defined as Aα is made up of members whose membership is not less than α, Aα=x∈X∣μA(x)≥α. α-cut set of fuzzy set is crisp set.Definition 8.
A fuzzy graphG=(V,σ,μ) is an algebraic structure of nonempty set V together with a pair of functions σ:V→[0,1] and μ:V×V→[0,1] such that for all u,v∈V, μ(u,v)≤σ(u)∧σ(v) and μ is a symmetric fuzzy relation on σ. Here σ(u) and μ(u,v) represent the membership values of the vertex u and of the edge (u,v) in G, respectively.In this paper, we denoteu∧v=min⁡{u,v} and u∨v=max⁡{u,v}. Here, we considered fuzzy graph G is simple (with no loops and parallel edges), finite, and undirected. μ is reflective (that is, μv,v=σv, for all v∈V) and symmetric (that is, μu,v=μv,u, for all (u,v)∈E).Note that a fuzzy graph is a generalization of crisp graph in whichσ(v)=1 for all v∈V and μu,v=1 if u,v∈E and μu,v=0 if u,v∉E. So, all the crisp graphs are fuzzy graphs but all fuzzy graphs are not crisp graphs.Definition 9.
The fuzzy graphG′=(V,σ′,μ′) is called a fuzzy subgraph ofGif for each two elements u,v∈V, we have σ′(u)≤σ(u) and μ′(u,v)≤μ(u,v).Definition 10.
The fuzzy graphG=(V,σ,μ) is called connected if, for every two elements u,v∈V, there exists a sequence of elements u0,u1,…,um such that u0=u, um=v, and μ(ui,ui+1)>0, (0≤i≤m-1).Definition 11.
For any fuzzy graphG=(V,σ,μ), let L={σ(u)>0∣u∈V}∪{μ(u,v)>0∣u≠v,u,v∈V} with k elements. Now assume L={α1,α2,…,αk} such that α1<α2<⋯<αk. The sequence {α1,α2,…,αk} and the set L are called the fundamental sequence and the fundamental set (or level set) of G, respectively.Definition 12.
The underlying crisp graphG∗=(V∗,E∗) of a fuzzy graph G=(V,σ,μ) is such that V∗=u∈V∣σ(u)>0 and E∗=u,v∣μ(u,v)>0.Definition 13.
Forα∈0,1, α-cut graph of a fuzzy graph G=(V,σ,μ) is a crisp graph Gα=(Vα,Eα) such that Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. It is obvious that a fuzzy graph will have a finite number of different α-cuts.


## 2.3. Basic Definitions in Fuzzy Coloring of Fuzzy Graphs

The concept of chromatic number of fuzzy graph was introduced by Munoz et al. [22]. The authors considered fuzzy graphs with crisp vertex set, that is, fuzzy graphs, for which σ(v)=1 for all v∈V and edges with membership degree in [0,1].Definition 14 (see [22]).
IfG=(V,μ) is such a fuzzy graph where V={1,2,3...n} and μ is a fuzzy number on the set of all subsets of V×V, assume I=A∪{0}, where A={α1<α2<…<αk} is the fundamental set (level set) of G. For each α∈I, Gα denote the crisp graph Gα=(V,Eα), where Eα=ij1≤i<j≤n,μ(i,j)≥α} and χα=χ(Gα) denote the chromatic number of crisp graph Gα.By this definition the chromatic number of fuzzy graphs G is the fuzzy numberχ(G)={(i,v(i))/i∈X}, where vi=max⁡α∈I∣i∈Aα and Aα={1,2,3…,χα}.Later Eslahchi and Onagh [21] introduced fuzzy vertex coloring of fuzzy graph. They defined fuzzy chromatic number as the least value of k for which the fuzzy graph G has k-fuzzy coloring as follows.Definition 15 (see [21]).
A familyΓ={γ1,γ2,…,γk} of fuzzy sets on a set V is called a k-fuzzy coloring of G=(V,σ,μ) if(i)
∨Γ=σ,(ii)
γi∧γj=0,(iii)
for every strong edge(x,y) (i.e., μ(x,y)>0 ) of G, min⁡{γi(x),γi(y)}=0 (1≤i≤k).Definition 16 (see [21]).
The minimum numberk for which there exists a k-fuzzy coloring is called the fuzzy chromatic number of G, denoted as χfG.Incorporating the features of the above two definitions, Kishore and Sunitha [23] modified the chromatic number χ(G) of fuzzy graph as follows.Definition 17 (see [23]).
For eachαϵI, Gα denote the crisp graph Gα=(σα,μα) and χα=χ(Gα) denote the chromatic number of crisp graph Gα. The chromatic number of fuzzy graph G=(V,σ,μ) is the number χG=max⁡{χGα∣α∈A}.


## 3. Fuzzy Chromatic Polynomial of a Fuzzy Graph

A fuzzy chromatic polynomial is a polynomial which is associated with the fuzzy coloring of fuzzy graphs. Therefore, chromatic polynomial in fuzzy graph is called fuzzy chromatic polynomial of fuzzy graph. In this section, we define the concept of fuzzy chromatic polynomial of a fuzzy graph based onα-cuts of fuzzy graph which are crisp graphs. Furthermore, we determine the fuzzy chromatic polynomials for some fuzzy graphs with crisp and fuzzy vertices.Crisp vertex coloring and the chromatic polynomial ofα-cut graph of the fuzzy graph are defined as follows.Definition 18.
LetG=(V,σ,μ) be a fuzzy graph and Gα denote α-cut graph of the fuzzy graph G which is a crisp graph Gα=(Vα,Eα), α∈0,1. A function Cαk:Vα→{1,2,…,k}, k∈N is called a k-coloring (crisp vertex coloring) of Gα if Cαk(vi)≠Cαk(vj) whenever the vertices vi and vj are adjacent in Gα.Definition 19.
The number of distinct k-coloring on the vertices ofGα is called the chromatic polynomial of Gα. It is denoted by P(Gα,k).LetGα∣α∈I be the family of α-cuts sets of G, where the α-cut of a fuzzy graph is the crisp graph Gα. Hence, any crisp k-coloring Cαk can be defined on the vertex set of Gα. The k-coloring function of the fuzzy graph G is defined through this sequence. For each α∈I, let the fuzzy chromatic polynomial of G be defined through a monotone family of sets.Fuzzy chromatic polynomial of a fuzzy graph is defined as follows.Definition 20.
LetG be a fuzzy graph. The fuzzy chromatic polynomial of G is defined as the chromatic polynomial of its crisp graphs Gα, for α∈I. It is denoted by Pαf(G,k).That is,PαfG,k=P(Gα,k), ∀α∈I.


### 3.1. Fuzzy Chromatic Polynomial of Fuzzy Graph with Crisp Vertices

In this subsection, we present fuzzy chromatic polynomial of fuzzy graphs with crisp vertices and fuzzy edges.A fuzzy graphG with crisp vertices and fuzzy edges, and α-cut graph of G are defined as follows.Definition 21.
A fuzzy graph is defined as a pairG=(V,μ) such that(1)
V is the crisp set of vertices (that is,σu=1,∀u∈V);(2)
the functionμ:VxV→[0,1] is defined by μu,v≤σ(u)∧σ(v), for all u,v∈V.Definition 22.
LetG=(V,μ) be a fuzzy graph. For α∈I, α-cut graph of the fuzzy graph G is defined as the crisp graph Gα=V,Eα, where Eα=u,v,u,v∈V∣μ(u,v)≥α.Example 23.
Consider the fuzzy graphG with crisp vertices and fuzzy edges in Figure 1.Figure 1
The fuzzy graphG with crisp vertices and fuzzy edges.InG, we consider I={0,0.2,0.3,0.5,0.8,1}; for each α∈I, we have a crisp graph Gα and its chromatic polynomial which is the fuzzy chromatic polynomial of the fuzzy graph G is obtained (see Figure 2). (The integers in the brackets denote the number of ways of coloring the vertices.)Figure 2
Different fuzzy chromatic polynomials of the fuzzy graphG in Example 23.Remark 24.
The fuzzy chromatic polynomial depends on the values ofα, which means the fuzzy chromatic polynomial varies for the same fuzzy graph G for different values of α.For the fuzzy graphG in Example 23, the fuzzy chromatic polynomial varies for different values of α as shown below: (3)PαfG,k=kk-1k-2k-3,α=0kk-1k-22,α=0.2kk-12k-2,α=0.3kk-13,α=0.5k2k-12,α=0.8k4,α=1Remark 25.
The fuzzy chromatic polynomial of a fuzzy graph does not need to be decreased when the value ofα increases. Let us consider α1=0.2, α2=0.3, α3=0.5, α4=0.8, and α5=1 for the fuzzy graph G in Example 23, but PαifG,k, k≥χαi, where χαi is the chromatic number of the crisp graph Gαi i=1,2,3,4,5 is not decreased as αi increases. For instance, Pα1fG,χα1=6, Pα2fG,χα2=12, Pα3fG,χα3=2, Pα4fG,χα4=4, and Pα5fG,χα5=1.Remark 26.
LetG be a fuzzy graph with n vertices. Then for G with crisp vertices and fuzzy edges and for α=1, PαfG,k is not always P(Nn,k), where Nn is the null crisp graph with n vertices which is clear from the following example.Example 27.
Consider the fuzzy graphG given in Figure 3(a). In Figure 3(a), for α=1, Gα is a crisp graph in Figure 3(b). But Gα is not a null crisp graph with three vertices. Thus, PαfG,k≠PN3,k.Figure 3 (a)
A fuzzy graphG (b)
A crisp graphGα for α=1The following result gives the degree of fuzzy chromatic polynomial of fuzzy graph with crisp vertices and fuzzy edges are equal to the number of vertices in crisp vertex set.Lemma 28.
LetG=(V,μ) be a fuzzy graph with crisp vertices and fuzzy edges. Then the degree of PαfG,k=V, for all α∈I.Proof.
LetG=(V,μ) be a fuzzy graph with crisp vertices and fuzzy edges. Now, Gα=(V,Eα), where Eα=u,v∣μ(u,v)≥α. We know that the degree of the chromatic polynomial of a crisp graph Gα is the number of vertices of Gα. That is, the degree of PGα,k=V. By Definition 20, we have PαfG,k=P(Gα,k), for α∈I. From this it follows that the degree of PαfG,k is equal to the degree of PGα,k. Therefore, PαfG,k=V.


### 3.2. Fuzzy Chromatic Polynomial of Fuzzy Graph with Fuzzy Vertices

In Section3.1, we introduced the fuzzy chromatic polynomial of fuzzy graph G=(V,μ), where V is crisp set vertices and E is fuzzy set of edges. In this subsection, we present fuzzy chromatic polynomial of fuzzy graphs with fuzzy vertex set and fuzzy edge set. Here, we use Definition 8 for fuzzy graph and Definition 13 for α-cut graph which are presented in Section 2.Example 29.
Consider a fuzzy graphG with fuzzy vertex set and fuzzy edge set in Figure 4Figure 4
A fuzzy graphG with fuzzy vertices and fuzzy edges.InG, we consider I={0,0.2,0.3,0.4,0.6,0.8}; for each α∈I, we have a crisp graph Gα and its chromatic polynomial which is the fuzzy chromatic polynomial of the fuzzy graph G is obtained (see Figure 5). (The integers in the brackets denote the number of ways of coloring the vertices.)Figure 5
Different fuzzy chromatic polynomials of the fuzzy graph G in Example29.Remark 30.
The fuzzy chromatic polynomial varies for the same fuzzy graphG for different values of α. It is clear from Example 29. Here, the fuzzy chromatic polynomial of the fuzzy graph in Example 29 is given below. (4)PαfG,k=kk-1k-2k-3k-4,α=0kk-1k-23,α=0.2k2k-13,α=0.3k5,α=0.4k3,α=0.6k,α=0.8Remark 31.
For fuzzy graphG with fuzzy vertex set and fuzzy edge set, the degree of the fuzzy chromatic polynomial of G is not always equal to the number of vertices of G. It can be easily seen from the fuzzy chromatic polynomial of the fuzzy graph in Example 29.
For instance, forα=0.4, the degree of PαfG,k=5 which is the number of vertices of G, but for α=0.6, the degree of PαfG,k=3≠5; also for α=0.8, the degree of PαfG,k=1≠5.Remark 32.
The fuzzy chromatic polynomial of fuzzy graphG with fuzzy vertex set and fuzzy edge set, PαfG,k,k≥χα will be decreased when the value of α will increase, since in fuzzy graph with fuzzy vertices and fuzzy edges, both Vα and Eα decrease as α increases (see Table 1).Table 1
The values ofα, Vα, Eα, χα, and PαfG,k, k≥χα for the fuzzy graph G in Example 33.
α V α E α χ α P α f G , k P α f G , χ α P α f G , χ α + 1 P α f G , χ α + 2 P α f G , χ α + 3 0 3 3 3 k(k-1)(k-2) 6 24 60 120 0.1 3 3 3 k(k-1)(k-2) 6 24 60 120 0.5 3 2 2 k(k-1)2 2 12 36 80 0.7 2 1 2 k(k-1) 2 6 12 20 0.8 2 0 1 k2 1 4 9 16 1 1 0 1 k 1 2 3 4Example 33.
Consider a fuzzy graphG with fuzzy vertex set and fuzzy edge set in Figure 6.Figure 6
A fuzzy graphG.By routine computation, the fuzzy chromatic polynomial of the fuzzy graphG in Figure 6 is obtained as(5)PαfG,k=kk-1k-2,α=0kk-1k-2,α=0.1kk-12,α=0.5kk-1,α=0.7k2,α=0.8k,α=1Table1 shows that the fuzzy chromatic polynomial of the fuzzy graph G in Example 33 deceases as α increases (see column 1 and columns 6-9 of Table 1). Moreover, both the number of vertices and the number of edges of α-cut graph of the fuzzy graph decrease as α increases (see column 1 and columns 2 and 3 of Table 1).


## 3.1. Fuzzy Chromatic Polynomial of Fuzzy Graph with Crisp Vertices

In this subsection, we present fuzzy chromatic polynomial of fuzzy graphs with crisp vertices and fuzzy edges.A fuzzy graphG with crisp vertices and fuzzy edges, and α-cut graph of G are defined as follows.Definition 21.
A fuzzy graph is defined as a pairG=(V,μ) such that(1)
V is the crisp set of vertices (that is,σu=1,∀u∈V);(2)
the functionμ:VxV→[0,1] is defined by μu,v≤σ(u)∧σ(v), for all u,v∈V.Definition 22.
LetG=(V,μ) be a fuzzy graph. For α∈I, α-cut graph of the fuzzy graph G is defined as the crisp graph Gα=V,Eα, where Eα=u,v,u,v∈V∣μ(u,v)≥α.Example 23.
Consider the fuzzy graphG with crisp vertices and fuzzy edges in Figure 1.Figure 1
The fuzzy graphG with crisp vertices and fuzzy edges.InG, we consider I={0,0.2,0.3,0.5,0.8,1}; for each α∈I, we have a crisp graph Gα and its chromatic polynomial which is the fuzzy chromatic polynomial of the fuzzy graph G is obtained (see Figure 2). (The integers in the brackets denote the number of ways of coloring the vertices.)Figure 2
Different fuzzy chromatic polynomials of the fuzzy graphG in Example 23.Remark 24.
The fuzzy chromatic polynomial depends on the values ofα, which means the fuzzy chromatic polynomial varies for the same fuzzy graph G for different values of α.For the fuzzy graphG in Example 23, the fuzzy chromatic polynomial varies for different values of α as shown below: (3)PαfG,k=kk-1k-2k-3,α=0kk-1k-22,α=0.2kk-12k-2,α=0.3kk-13,α=0.5k2k-12,α=0.8k4,α=1Remark 25.
The fuzzy chromatic polynomial of a fuzzy graph does not need to be decreased when the value ofα increases. Let us consider α1=0.2, α2=0.3, α3=0.5, α4=0.8, and α5=1 for the fuzzy graph G in Example 23, but PαifG,k, k≥χαi, where χαi is the chromatic number of the crisp graph Gαi i=1,2,3,4,5 is not decreased as αi increases. For instance, Pα1fG,χα1=6, Pα2fG,χα2=12, Pα3fG,χα3=2, Pα4fG,χα4=4, and Pα5fG,χα5=1.Remark 26.
LetG be a fuzzy graph with n vertices. Then for G with crisp vertices and fuzzy edges and for α=1, PαfG,k is not always P(Nn,k), where Nn is the null crisp graph with n vertices which is clear from the following example.Example 27.
Consider the fuzzy graphG given in Figure 3(a). In Figure 3(a), for α=1, Gα is a crisp graph in Figure 3(b). But Gα is not a null crisp graph with three vertices. Thus, PαfG,k≠PN3,k.Figure 3 (a)
A fuzzy graphG (b)
A crisp graphGα for α=1The following result gives the degree of fuzzy chromatic polynomial of fuzzy graph with crisp vertices and fuzzy edges are equal to the number of vertices in crisp vertex set.Lemma 28.
LetG=(V,μ) be a fuzzy graph with crisp vertices and fuzzy edges. Then the degree of PαfG,k=V, for all α∈I.Proof.
LetG=(V,μ) be a fuzzy graph with crisp vertices and fuzzy edges. Now, Gα=(V,Eα), where Eα=u,v∣μ(u,v)≥α. We know that the degree of the chromatic polynomial of a crisp graph Gα is the number of vertices of Gα. That is, the degree of PGα,k=V. By Definition 20, we have PαfG,k=P(Gα,k), for α∈I. From this it follows that the degree of PαfG,k is equal to the degree of PGα,k. Therefore, PαfG,k=V.


## 3.2. Fuzzy Chromatic Polynomial of Fuzzy Graph with Fuzzy Vertices

In Section3.1, we introduced the fuzzy chromatic polynomial of fuzzy graph G=(V,μ), where V is crisp set vertices and E is fuzzy set of edges. In this subsection, we present fuzzy chromatic polynomial of fuzzy graphs with fuzzy vertex set and fuzzy edge set. Here, we use Definition 8 for fuzzy graph and Definition 13 for α-cut graph which are presented in Section 2.Example 29.
Consider a fuzzy graphG with fuzzy vertex set and fuzzy edge set in Figure 4Figure 4
A fuzzy graphG with fuzzy vertices and fuzzy edges.InG, we consider I={0,0.2,0.3,0.4,0.6,0.8}; for each α∈I, we have a crisp graph Gα and its chromatic polynomial which is the fuzzy chromatic polynomial of the fuzzy graph G is obtained (see Figure 5). (The integers in the brackets denote the number of ways of coloring the vertices.)Figure 5
Different fuzzy chromatic polynomials of the fuzzy graph G in Example29.Remark 30.
The fuzzy chromatic polynomial varies for the same fuzzy graphG for different values of α. It is clear from Example 29. Here, the fuzzy chromatic polynomial of the fuzzy graph in Example 29 is given below. (4)PαfG,k=kk-1k-2k-3k-4,α=0kk-1k-23,α=0.2k2k-13,α=0.3k5,α=0.4k3,α=0.6k,α=0.8Remark 31.
For fuzzy graphG with fuzzy vertex set and fuzzy edge set, the degree of the fuzzy chromatic polynomial of G is not always equal to the number of vertices of G. It can be easily seen from the fuzzy chromatic polynomial of the fuzzy graph in Example 29.
For instance, forα=0.4, the degree of PαfG,k=5 which is the number of vertices of G, but for α=0.6, the degree of PαfG,k=3≠5; also for α=0.8, the degree of PαfG,k=1≠5.Remark 32.
The fuzzy chromatic polynomial of fuzzy graphG with fuzzy vertex set and fuzzy edge set, PαfG,k,k≥χα will be decreased when the value of α will increase, since in fuzzy graph with fuzzy vertices and fuzzy edges, both Vα and Eα decrease as α increases (see Table 1).Table 1
The values ofα, Vα, Eα, χα, and PαfG,k, k≥χα for the fuzzy graph G in Example 33.
α V α E α χ α P α f G , k P α f G , χ α P α f G , χ α + 1 P α f G , χ α + 2 P α f G , χ α + 3 0 3 3 3 k(k-1)(k-2) 6 24 60 120 0.1 3 3 3 k(k-1)(k-2) 6 24 60 120 0.5 3 2 2 k(k-1)2 2 12 36 80 0.7 2 1 2 k(k-1) 2 6 12 20 0.8 2 0 1 k2 1 4 9 16 1 1 0 1 k 1 2 3 4Example 33.
Consider a fuzzy graphG with fuzzy vertex set and fuzzy edge set in Figure 6.Figure 6
A fuzzy graphG.By routine computation, the fuzzy chromatic polynomial of the fuzzy graphG in Figure 6 is obtained as(5)PαfG,k=kk-1k-2,α=0kk-1k-2,α=0.1kk-12,α=0.5kk-1,α=0.7k2,α=0.8k,α=1Table1 shows that the fuzzy chromatic polynomial of the fuzzy graph G in Example 33 deceases as α increases (see column 1 and columns 6-9 of Table 1). Moreover, both the number of vertices and the number of edges of α-cut graph of the fuzzy graph decrease as α increases (see column 1 and columns 2 and 3 of Table 1).


## 4. Main Results

In this section, we prove some relevant results on fuzzy chromatic polynomial for fuzzy graphs which are discussed in Section3. Moreover, the fuzzy chromatic polynomial of complete fuzzy graph and the fuzzy chromatic polynomial of fuzzy graphs which are cycles and fuzzy cycles are studied.


### 4.1.α-Cut Graph and Fuzzy Graph

The relations among differentα-cuts of a fuzzy graph have been established as follows.Lemma 34.
LetG be a fuzzy graph. If 0≤α≤β≤1, then the following are true.(i)
Vα≥Vβ(ii)
Eα≥EβProof.
LetG=(V,σ,μ) be a fuzzy graph and 0≤α≤β≤1. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Also, Gβ=(Vβ,Eβ), where Vβ=u∈V∣σ(u)≥β and Eβ=u,v∣μ(u,v)≥β. Since 0≤α≤β≤1, we have Vβ⊆Vα and Eβ⊆Eα. From this, results (i) and (ii) hold.Theorem 35.
LetG be a fuzzy graph. If 0≤α≤β≤1, then Gβ is a subgraph of Gα.Proof.
LetG=(V,σ,μ) be a fuzzy graph and 0≤α≤β≤1. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Also, Gβ=(Vβ,Eβ), where Vβ=u∈V∣σ(u)≥β and Eβ=u,v∣μ(u,v)≥β. From Lemma 34, we get Vβ⊆Vα and Eβ⊆Eα. That means, for any element u∈Vβ, u∈Vα and for any element (u,v)∈Eβ, (u,v)∈Eα. Hence, Gβ is a subgraph of Gα.Theorem 36.
LetG be a fuzzy graph. If 0≤α≤β≤1, then deg PGα,k≥ deg PGβ,k.Proof.
LetG=(V,σ,μ) be a fuzzy graph and 0≤α≤β≤1. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Also, Gβ=(Vβ,Eβ), where Vβ=u∈V∣σ(u)≥β and Eβ=u,v∣μ(u,v)≥β. We know that the degree of the chromatic polynomial of a crisp graph is the number of vertices in the crisp graph. Therefore, the degree of PGα,k=Vα and the degree of PGβ,k=Vβ. By Lemma 34(i), we have Vα≥Vβ. Therefore, deg PGα,k=Vα≥Vβ= deg PGβ,k.The relations between theα-cut graph of a fuzzy graph and the value of α=0, the fuzzy chromatic polynomial of a fuzzy graph, and the chromatic polynomial of corresponding complete crisp graph can be determined below.Lemma 37.
LetG be a fuzzy graph with n vertices and Gα be α-cut of G. Then if α=0, then Gα is a complete crisp graph with n vertices.Proof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices and α=0. Now, G0=(V0,E0), where V0=u∈V∣σ(u)≥0 and E0=u,v∣μ(u,v)≥0. Here, V0 consists of all the vertices in V of G. Similarly, E0 consists of all the edges in E and all the edges not in E of G. This shows that all the vertices in V0 of G0 are adjacent to each other. Therefore, G0 is a complete crisp graph of n vertices. This completes the proof.Remark 38.
Forα-cut of the fuzzy graph G with n vertices, Gα=Kn if α=0.Theorem 39.
LetG be a fuzzy graph with n vertices and Gα be α-cut of G. Then if α=0, (6)PαfG,k=PKn,kProof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices and α=0. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Since G is fuzzy graph. Then by Definition 20 and Remark 38, the result holds.The relation between fuzzy chromatic polynomial of a fuzzy graph and the chromatic polynomial of corresponding underlying crisp graph is established below.Theorem 40.
LetG be a fuzzy graph and G∗ be its underlying crisp graph. If α=min⁡L, where L is the level set or fundamental set of G, then PαfG,k=P(G∗,k).Proof.
LetG=(V,σ,μ) be a fuzzy graph and let G∗=(V∗,E∗) be the underlying crisp graph of G, where V∗=u∈V∣σ(u)>0 and E∗=u,v,u,v∈V∣μ(u,v)>0. This means that V∗=V and E∗ consists of all the edges in E. Let L={α1,α2,...,αk} be a level set or fundamental set of G. Put α=min⁡L; now Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Since α is the minimum value in the level set L, Vα consists of all the vertices of V and Eα consists of all the edges in E. Therefore, Gα=G∗. Since G is fuzzy graph, then, by Definition 20, we have PαfG,k=PGα,k=PG∗,k.The following is an important theorem for computing the fuzzy chromatic polynomial of a fuzzy graph explicitly.Theorem 41.
LetG be a fuzzy graph with n vertices and G∗ be its underlying crisp graph. If α∈I=L∪{0} and β=min⁡L, then (7)PαfG,k=PKn,kifα=0PG∗,kifα=βPGα,kifβ<α≤1where Kn is a complete crisp graph with n vertices.Proof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices and let G∗=(V∗,E∗) be the underlying crisp graph of G, where V∗=u∈V∣σ(u)>0 and E∗=u,v,u,v∈V∣μ(u,v)>0. For α∈I, now Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Let us prove the theorem by considering three cases.
Case 1. Let α=0. Then by Theorem 39, the fuzzy chromatic polynomial of the fuzzy graph G is the chromatic polynomial of a complete crisp graph with n vertices, Kn. That is,(8)PαfG,k=PKn,k
Case 2. Let α=β, where β=min⁡L. Then by Theorem 40, the fuzzy chromatic polynomial of the fuzzy graph G is the chromatic polynomial of its underlying crisp graph G∗. That is, (9)PαfG,k=PG∗,k
Case 3. Let β<α≤1; since α is in I, then by Definition 20PαfG,k=PGα,k. This completes the proof.The following result shows that the degree of fuzzy chromatic polynomial of a fuzzy graph is less than or equal to the number of vertices of the fuzzy graph. It is a significant difference from crisp graph theory.Theorem 42.
LetG=(V,σ,μ) be a fuzzy graph. Then the degree of PαfG,k≤V,∀α∈I.Proof.
Let us prove the theorem by considering two cases.
Case 1. Let G=(V,μ) be a fuzzy graph with crisp vertices and fuzzy edges. By Lemma 28, the degree of PαfG,k=V,∀α∈I. Therefore, the result holds.
Case 2. Let G=(V,σ,μ) be a fuzzy graph with fuzzy vertex set and fuzzy edge set. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. We know that the degree of the chromatic polynomial of a crisp graph Gα is the number of vertices of Gα. That is, the degree of PGα,k=Vα. But for all α∈I, Vα≤V, since Vα⊆ V. Then by Definition 20, we have PαfG,k=PGα,k, for α∈I. Therefore, the degree of PαfG,k = the degree of PGα,k=Vα≤V. This implies that PαfG,k≤V,∀α∈I. Hence, from Case 1 and Case 2, we conclude that, for any fuzzy graph G, the degree of PαfG,k≤V, ∀α∈I.


### 4.2. Complete Fuzzy Graph and Fuzzy Cycle

In 1989, Bhutani [11] introduced the concept of a complete fuzzy graph as follows.Definition 43 (see [11]).
A complete fuzzy graph is a fuzzy graphG=(V,σ,μ) such that μu,v=σ(u)∧σ(v) for all u,v∈V.The following result gives the underlying crisp graph of a complete fuzzy graph is a complete crisp graph.Lemma 44.
LetG be a complete fuzzy graph and G∗ be its underlying crisp graph. Then G∗ is a complete crisp graph.It is clear from the following example.Example 45.
We show that the underlying crisp graph of a complete fuzzy graph is complete crisp graph. LetV=u,v,w,x. Define the fuzzy set σ on V as σu=0.7,σv=0.8,σw=1, and σx=0.6. Define a fuzzy set μ on E such that μu,v=μu,w=0.7,μu,x=μv,x=μw,x=0.6, and μv,w=0.8. Then μu,v=σu∧σ(v) for all u,v∈V. Thus, G=(V,σ,μ) is a complete fuzzy graph. Now,G∗=V∗,E∗, where V∗=u∈Vσu>0=u,v,w,x and E∗=u,v,u,v∈Vμu,v>0={u,v,u,w,u,x,v,x,w,x,v,w}. This shows that each vertex in G∗ joins each of the other vertices in G∗ exactly by one edge. Therefore, G∗ is a complete crisp graph K4.Remark 46.
For complete fuzzy graphG with n vertices, by Lemma 44, G∗=Kn, where Kn is a complete crisp graph.The following is an important theorem for computing the fuzzy chromatic polynomial of a complete fuzzy graph explicitly.Theorem 47.
LetG be a complete fuzzy graph with n vertices. If α∈I=L∪{0} and β=min⁡(L) then (10)PαfG,k=PKn,kifα=0andβPGα,kifβ<α≤1Proof.
LetG=(V,σ,μ) be a complete fuzzy graph with n vertices and let G∗=(V∗,E∗) be the underlying crisp graph of G, where V∗=u∈V∣σ(u)>0 and E∗=u,v,u,v∈V∣μ(u,v)>0. For α∈I=L∪{0}, where L is a level set of G now Gα=(Vα,Eα) where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Let us prove the theorem by considering three cases.
Case 1. Let α=0, and since G is a fuzzy graph with n vertices then, by Theorem 39, we have PαfG,k=PKn,k.
Case 2. Let α=β, where β=min⁡L; since G is a fuzzy graph then, by Theorem 40, we have(11)PαfG,k=PG∗,kand since G is complete fuzzy graph, then, by Remark 46 and (11), we get PαfG,k=PKn,k.
Case 3. Let β<α≤1; since α is in I and G is a fuzzy graph then by Theorem 41PαfG,k=PGα,k. This completes the proof.Remark 48.
For a complete fuzzy graphG=(V,σ,μ) with crisp vertices (i.e., σv=1,∀v∈V) and V=n, PαfG,k=PKn,k for all α∈I.The fuzzy chromatic polynomial of a complete fuzzy graph withL=V can be defined in terms of the chromatic polynomial of complete crisp graph as follows.Definition 49.
LetG=(V,σ,μ) be a complete fuzzy graph with V=n vertices. Let L be a level set of G and α∈I=LU{0}. Define β0=min⁡(L)=β, β1=min(L\β0), β2=min(L\β0,β1), …,βn-1=min(L\β0,β1,…,βn-2).IfL=V=n,n≥1, then the fuzzy chromatic polynomial of a complete fuzzy graph G is defined as (12)PαfG,k=PKn,kifα=0&β0PKn-1,kifα=β1PKn-2,kifα=β2⋮⋮PK1,kifα=βn-1where Kn, n≥1 is a complete crisp graph with n vertices.Note that the advantage of Definition49 is that the fuzzy chromatic polynomial of a complete fuzzy graph with V=L can be obtained without using the formal procedures. This situation can be illustrated in the following example.Example 50.
Consider the complete fuzzy graphG in Figure 7.Figure 7
A complete fuzzy graphG with V=L.In Figure7, V=4, I=L∪0, where L={0.6,0.7,0.8,1}. Therefore, L=4. Also, β0=0.6,β1=0.7, β2=0.8, and β3=1.SinceL=V=4, then, by Definition 49, the fuzzy chromatic polynomial of the complete fuzzy graph G is(13)PαfG,k=kk-1k-2k-3,α=0&0.6kk-1k-2,α=0.7kk-1,α=0.8k,α=1A fuzzy graph is a cycle and a fuzzy cycle as defined in [9, 32].Definition 51 (see [9, 32]).
LetG=(V,σ,μ) be a fuzzy graph. Then(i)
Gis called a cycle if G∗=(V∗,E∗) is a cycle;(ii)
Gis called a fuzzy cycle if G∗=(V∗,E∗) is a cycle and ∄ unique (x,y)∈E∗ such that μ(x,y)=∧{μ(u,v)∣(u,v)∈E∗}.Remark 52.
If a fuzzy graphG is cycle with n vertices, then G∗=Cn, where Cn is a cycle crisp graph with n vertices.The following theorem is important for computing the fuzzy chromatic polynomial of a fuzzy graph which is cycle.Theorem 53.
LetG be a fuzzy graph with n vertices. Then G is a cycle if and only if(14)PαfG,k=PKn,kifα=0PCn,kifα=βPGα,kifβ<α≤1where Kn and Cn are a complete crisp graph and cycle crisp graph with n vertices, respectively.Proof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices. Suppose G be a cycle. Since G is a cycle, G∗ is a cycle crisp graph. For α∈I=L∪{0}, where L is a level set of G, now Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Let us prove the theorem by considering three cases.
Case 1. Let α=0, and since G is a fuzzy graph with n vertices then by Theorem 39, we have PαfG,k=PKn,k.
Case 2. Let α=β, where β=min⁡L; since G is a fuzzy graph then, by Theorem 40, we have (15)PαfG,k=PG∗,kand since G is cycle with n vertices, then, by Remark 52 and (15), we get PαfG,k=PCn,k.
Case 3. Let β<α≤1; since α is in I and G is a fuzzy graph then, by Theorem 41, PαfG,k=PGα,k. Hence, the result holds.
Conversely, we shall prove it by contrapositive. SupposeG is not a cycle. Then, by Definition 51, G∗ is not a cycle. This implies that G∗≠Cn. Hence,(16)PαfG,k≠PKn,kifα=0PCn,kifα=βPGα,kifβ<α≤1Therefore, if (14) is true, then G is a cycle. This completes the proof.Corollary 54.
LetG be a fuzzy graph.If G is a fuzzy cycle with n vertices; then (14) is true.Proof.
LetG be a fuzzy cycle with n vertices. Since G is fuzzy cycle, then its G∗ is cycle. Then by Definition 51, G is a cycle. Then by Theorem 53, the result is immediate.Remark 55.
The converse of Corollary54 is not true. It can be seen from the following example.Example 56.
Consider the fuzzy graphG given in Figure 8.Figure 8
A fuzzy graphG.In Figure8, clearly G∗ is a cycle. So, G is cycle. For α∈I=L∪0,where L={0.2,0.6,0.8,1}, since G is cycle, then, by (14), the fuzzy chromatic polynomial of G is (17)PαfG,k=PK4,kifα=0PC4,kifα=0.2PGα,kif0.2<α≤1But G is not fuzzy cycle.Remark 57.
In general, the meaning of fuzzy chromatic polynomial of a fuzzy graph depends on the sense of the indexα. It can be interpreted that for lower values of α more numbers of different k-colorings are obtained. On the other hand, for higher values of α less number of different k-colorings are obtained. Therefore, the fuzzy chromatic polynomial sums up all this information so as to manage the fuzzy problem.


## 4.1.α-Cut Graph and Fuzzy Graph

The relations among differentα-cuts of a fuzzy graph have been established as follows.Lemma 34.
LetG be a fuzzy graph. If 0≤α≤β≤1, then the following are true.(i)
Vα≥Vβ(ii)
Eα≥EβProof.
LetG=(V,σ,μ) be a fuzzy graph and 0≤α≤β≤1. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Also, Gβ=(Vβ,Eβ), where Vβ=u∈V∣σ(u)≥β and Eβ=u,v∣μ(u,v)≥β. Since 0≤α≤β≤1, we have Vβ⊆Vα and Eβ⊆Eα. From this, results (i) and (ii) hold.Theorem 35.
LetG be a fuzzy graph. If 0≤α≤β≤1, then Gβ is a subgraph of Gα.Proof.
LetG=(V,σ,μ) be a fuzzy graph and 0≤α≤β≤1. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Also, Gβ=(Vβ,Eβ), where Vβ=u∈V∣σ(u)≥β and Eβ=u,v∣μ(u,v)≥β. From Lemma 34, we get Vβ⊆Vα and Eβ⊆Eα. That means, for any element u∈Vβ, u∈Vα and for any element (u,v)∈Eβ, (u,v)∈Eα. Hence, Gβ is a subgraph of Gα.Theorem 36.
LetG be a fuzzy graph. If 0≤α≤β≤1, then deg PGα,k≥ deg PGβ,k.Proof.
LetG=(V,σ,μ) be a fuzzy graph and 0≤α≤β≤1. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Also, Gβ=(Vβ,Eβ), where Vβ=u∈V∣σ(u)≥β and Eβ=u,v∣μ(u,v)≥β. We know that the degree of the chromatic polynomial of a crisp graph is the number of vertices in the crisp graph. Therefore, the degree of PGα,k=Vα and the degree of PGβ,k=Vβ. By Lemma 34(i), we have Vα≥Vβ. Therefore, deg PGα,k=Vα≥Vβ= deg PGβ,k.The relations between theα-cut graph of a fuzzy graph and the value of α=0, the fuzzy chromatic polynomial of a fuzzy graph, and the chromatic polynomial of corresponding complete crisp graph can be determined below.Lemma 37.
LetG be a fuzzy graph with n vertices and Gα be α-cut of G. Then if α=0, then Gα is a complete crisp graph with n vertices.Proof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices and α=0. Now, G0=(V0,E0), where V0=u∈V∣σ(u)≥0 and E0=u,v∣μ(u,v)≥0. Here, V0 consists of all the vertices in V of G. Similarly, E0 consists of all the edges in E and all the edges not in E of G. This shows that all the vertices in V0 of G0 are adjacent to each other. Therefore, G0 is a complete crisp graph of n vertices. This completes the proof.Remark 38.
Forα-cut of the fuzzy graph G with n vertices, Gα=Kn if α=0.Theorem 39.
LetG be a fuzzy graph with n vertices and Gα be α-cut of G. Then if α=0, (6)PαfG,k=PKn,kProof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices and α=0. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Since G is fuzzy graph. Then by Definition 20 and Remark 38, the result holds.The relation between fuzzy chromatic polynomial of a fuzzy graph and the chromatic polynomial of corresponding underlying crisp graph is established below.Theorem 40.
LetG be a fuzzy graph and G∗ be its underlying crisp graph. If α=min⁡L, where L is the level set or fundamental set of G, then PαfG,k=P(G∗,k).Proof.
LetG=(V,σ,μ) be a fuzzy graph and let G∗=(V∗,E∗) be the underlying crisp graph of G, where V∗=u∈V∣σ(u)>0 and E∗=u,v,u,v∈V∣μ(u,v)>0. This means that V∗=V and E∗ consists of all the edges in E. Let L={α1,α2,...,αk} be a level set or fundamental set of G. Put α=min⁡L; now Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Since α is the minimum value in the level set L, Vα consists of all the vertices of V and Eα consists of all the edges in E. Therefore, Gα=G∗. Since G is fuzzy graph, then, by Definition 20, we have PαfG,k=PGα,k=PG∗,k.The following is an important theorem for computing the fuzzy chromatic polynomial of a fuzzy graph explicitly.Theorem 41.
LetG be a fuzzy graph with n vertices and G∗ be its underlying crisp graph. If α∈I=L∪{0} and β=min⁡L, then (7)PαfG,k=PKn,kifα=0PG∗,kifα=βPGα,kifβ<α≤1where Kn is a complete crisp graph with n vertices.Proof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices and let G∗=(V∗,E∗) be the underlying crisp graph of G, where V∗=u∈V∣σ(u)>0 and E∗=u,v,u,v∈V∣μ(u,v)>0. For α∈I, now Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Let us prove the theorem by considering three cases.
Case 1. Let α=0. Then by Theorem 39, the fuzzy chromatic polynomial of the fuzzy graph G is the chromatic polynomial of a complete crisp graph with n vertices, Kn. That is,(8)PαfG,k=PKn,k
Case 2. Let α=β, where β=min⁡L. Then by Theorem 40, the fuzzy chromatic polynomial of the fuzzy graph G is the chromatic polynomial of its underlying crisp graph G∗. That is, (9)PαfG,k=PG∗,k
Case 3. Let β<α≤1; since α is in I, then by Definition 20PαfG,k=PGα,k. This completes the proof.The following result shows that the degree of fuzzy chromatic polynomial of a fuzzy graph is less than or equal to the number of vertices of the fuzzy graph. It is a significant difference from crisp graph theory.Theorem 42.
LetG=(V,σ,μ) be a fuzzy graph. Then the degree of PαfG,k≤V,∀α∈I.Proof.
Let us prove the theorem by considering two cases.
Case 1. Let G=(V,μ) be a fuzzy graph with crisp vertices and fuzzy edges. By Lemma 28, the degree of PαfG,k=V,∀α∈I. Therefore, the result holds.
Case 2. Let G=(V,σ,μ) be a fuzzy graph with fuzzy vertex set and fuzzy edge set. Now, Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. We know that the degree of the chromatic polynomial of a crisp graph Gα is the number of vertices of Gα. That is, the degree of PGα,k=Vα. But for all α∈I, Vα≤V, since Vα⊆ V. Then by Definition 20, we have PαfG,k=PGα,k, for α∈I. Therefore, the degree of PαfG,k = the degree of PGα,k=Vα≤V. This implies that PαfG,k≤V,∀α∈I. Hence, from Case 1 and Case 2, we conclude that, for any fuzzy graph G, the degree of PαfG,k≤V, ∀α∈I.


## 4.2. Complete Fuzzy Graph and Fuzzy Cycle

In 1989, Bhutani [11] introduced the concept of a complete fuzzy graph as follows.Definition 43 (see [11]).
A complete fuzzy graph is a fuzzy graphG=(V,σ,μ) such that μu,v=σ(u)∧σ(v) for all u,v∈V.The following result gives the underlying crisp graph of a complete fuzzy graph is a complete crisp graph.Lemma 44.
LetG be a complete fuzzy graph and G∗ be its underlying crisp graph. Then G∗ is a complete crisp graph.It is clear from the following example.Example 45.
We show that the underlying crisp graph of a complete fuzzy graph is complete crisp graph. LetV=u,v,w,x. Define the fuzzy set σ on V as σu=0.7,σv=0.8,σw=1, and σx=0.6. Define a fuzzy set μ on E such that μu,v=μu,w=0.7,μu,x=μv,x=μw,x=0.6, and μv,w=0.8. Then μu,v=σu∧σ(v) for all u,v∈V. Thus, G=(V,σ,μ) is a complete fuzzy graph. Now,G∗=V∗,E∗, where V∗=u∈Vσu>0=u,v,w,x and E∗=u,v,u,v∈Vμu,v>0={u,v,u,w,u,x,v,x,w,x,v,w}. This shows that each vertex in G∗ joins each of the other vertices in G∗ exactly by one edge. Therefore, G∗ is a complete crisp graph K4.Remark 46.
For complete fuzzy graphG with n vertices, by Lemma 44, G∗=Kn, where Kn is a complete crisp graph.The following is an important theorem for computing the fuzzy chromatic polynomial of a complete fuzzy graph explicitly.Theorem 47.
LetG be a complete fuzzy graph with n vertices. If α∈I=L∪{0} and β=min⁡(L) then (10)PαfG,k=PKn,kifα=0andβPGα,kifβ<α≤1Proof.
LetG=(V,σ,μ) be a complete fuzzy graph with n vertices and let G∗=(V∗,E∗) be the underlying crisp graph of G, where V∗=u∈V∣σ(u)>0 and E∗=u,v,u,v∈V∣μ(u,v)>0. For α∈I=L∪{0}, where L is a level set of G now Gα=(Vα,Eα) where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Let us prove the theorem by considering three cases.
Case 1. Let α=0, and since G is a fuzzy graph with n vertices then, by Theorem 39, we have PαfG,k=PKn,k.
Case 2. Let α=β, where β=min⁡L; since G is a fuzzy graph then, by Theorem 40, we have(11)PαfG,k=PG∗,kand since G is complete fuzzy graph, then, by Remark 46 and (11), we get PαfG,k=PKn,k.
Case 3. Let β<α≤1; since α is in I and G is a fuzzy graph then by Theorem 41PαfG,k=PGα,k. This completes the proof.Remark 48.
For a complete fuzzy graphG=(V,σ,μ) with crisp vertices (i.e., σv=1,∀v∈V) and V=n, PαfG,k=PKn,k for all α∈I.The fuzzy chromatic polynomial of a complete fuzzy graph withL=V can be defined in terms of the chromatic polynomial of complete crisp graph as follows.Definition 49.
LetG=(V,σ,μ) be a complete fuzzy graph with V=n vertices. Let L be a level set of G and α∈I=LU{0}. Define β0=min⁡(L)=β, β1=min(L\β0), β2=min(L\β0,β1), …,βn-1=min(L\β0,β1,…,βn-2).IfL=V=n,n≥1, then the fuzzy chromatic polynomial of a complete fuzzy graph G is defined as (12)PαfG,k=PKn,kifα=0&β0PKn-1,kifα=β1PKn-2,kifα=β2⋮⋮PK1,kifα=βn-1where Kn, n≥1 is a complete crisp graph with n vertices.Note that the advantage of Definition49 is that the fuzzy chromatic polynomial of a complete fuzzy graph with V=L can be obtained without using the formal procedures. This situation can be illustrated in the following example.Example 50.
Consider the complete fuzzy graphG in Figure 7.Figure 7
A complete fuzzy graphG with V=L.In Figure7, V=4, I=L∪0, where L={0.6,0.7,0.8,1}. Therefore, L=4. Also, β0=0.6,β1=0.7, β2=0.8, and β3=1.SinceL=V=4, then, by Definition 49, the fuzzy chromatic polynomial of the complete fuzzy graph G is(13)PαfG,k=kk-1k-2k-3,α=0&0.6kk-1k-2,α=0.7kk-1,α=0.8k,α=1A fuzzy graph is a cycle and a fuzzy cycle as defined in [9, 32].Definition 51 (see [9, 32]).
LetG=(V,σ,μ) be a fuzzy graph. Then(i)
Gis called a cycle if G∗=(V∗,E∗) is a cycle;(ii)
Gis called a fuzzy cycle if G∗=(V∗,E∗) is a cycle and ∄ unique (x,y)∈E∗ such that μ(x,y)=∧{μ(u,v)∣(u,v)∈E∗}.Remark 52.
If a fuzzy graphG is cycle with n vertices, then G∗=Cn, where Cn is a cycle crisp graph with n vertices.The following theorem is important for computing the fuzzy chromatic polynomial of a fuzzy graph which is cycle.Theorem 53.
LetG be a fuzzy graph with n vertices. Then G is a cycle if and only if(14)PαfG,k=PKn,kifα=0PCn,kifα=βPGα,kifβ<α≤1where Kn and Cn are a complete crisp graph and cycle crisp graph with n vertices, respectively.Proof.
LetG=(V,σ,μ) be a fuzzy graph with n vertices. Suppose G be a cycle. Since G is a cycle, G∗ is a cycle crisp graph. For α∈I=L∪{0}, where L is a level set of G, now Gα=(Vα,Eα), where Vα=u∈V∣σ(u)≥α and Eα=u,v∣μ(u,v)≥α. Let us prove the theorem by considering three cases.
Case 1. Let α=0, and since G is a fuzzy graph with n vertices then by Theorem 39, we have PαfG,k=PKn,k.
Case 2. Let α=β, where β=min⁡L; since G is a fuzzy graph then, by Theorem 40, we have (15)PαfG,k=PG∗,kand since G is cycle with n vertices, then, by Remark 52 and (15), we get PαfG,k=PCn,k.
Case 3. Let β<α≤1; since α is in I and G is a fuzzy graph then, by Theorem 41, PαfG,k=PGα,k. Hence, the result holds.
Conversely, we shall prove it by contrapositive. SupposeG is not a cycle. Then, by Definition 51, G∗ is not a cycle. This implies that G∗≠Cn. Hence,(16)PαfG,k≠PKn,kifα=0PCn,kifα=βPGα,kifβ<α≤1Therefore, if (14) is true, then G is a cycle. This completes the proof.Corollary 54.
LetG be a fuzzy graph.If G is a fuzzy cycle with n vertices; then (14) is true.Proof.
LetG be a fuzzy cycle with n vertices. Since G is fuzzy cycle, then its G∗ is cycle. Then by Definition 51, G is a cycle. Then by Theorem 53, the result is immediate.Remark 55.
The converse of Corollary54 is not true. It can be seen from the following example.Example 56.
Consider the fuzzy graphG given in Figure 8.Figure 8
A fuzzy graphG.In Figure8, clearly G∗ is a cycle. So, G is cycle. For α∈I=L∪0,where L={0.2,0.6,0.8,1}, since G is cycle, then, by (14), the fuzzy chromatic polynomial of G is (17)PαfG,k=PK4,kifα=0PC4,kifα=0.2PGα,kif0.2<α≤1But G is not fuzzy cycle.Remark 57.
In general, the meaning of fuzzy chromatic polynomial of a fuzzy graph depends on the sense of the indexα. It can be interpreted that for lower values of α more numbers of different k-colorings are obtained. On the other hand, for higher values of α less number of different k-colorings are obtained. Therefore, the fuzzy chromatic polynomial sums up all this information so as to manage the fuzzy problem.


## 5. Conclusions

In this paper, the concept of fuzzy chromatic polynomial of fuzzy graph with crisp and fuzzy vertex sets is introduced. The fuzzy chromatic polynomial of fuzzy graph is defined based onα-cuts of the fuzzy graph. Some properties of the fuzzy chromatic polynomial of fuzzy graphs are investigated. The degree of fuzzy chromatic polynomial of a fuzzy graph is less than or equal to the number of vertices in fuzzy graph which is a significant difference from the crisp graph theory. Further, the fuzzy chromatic polynomial of fuzzy graph with fuzzy vertex set will decrease when the value of α will increase. Also, more results on fuzzy chromatic polynomial of fuzzy graphs have been proved. The relation between the fuzzy chromatic polynomial of fuzzy graph and its underlying crisp graph and the relation between the fuzzy chromatic polynomial of fuzzy graph and complete crisp graph are established. Finally, the fuzzy chromatic polynomial for complete fuzzy graph and fuzzy cycle is studied. Also, the fuzzy chromatic polynomial of complete fuzzy graph is defined explicitly when V=L. We are working on fuzzy chromatic polynomial based on different types of fuzzy coloring functions as an extension of this study.



---

*Source: 5213020-2019-05-02.xml*