Abstract

The article describes a new thought on the chromatic polynomial of an intuitionistic fuzzy graph which is illustrated based on -level graphs. Besides, the alpha-beta fundamental set of an intuitionistic fuzzy graph is also defined with a vivid description. In addition to that, some characterizations of the chromatic polynomial of an intuitionistic fuzzy graph are specified as well verified. Furthermore, some untouched properties of the -level graph are also projected and proved.

1. Introduction

Graph coloring has a lot of applications in areas such as wireless radio channel assignment [1], timetable scheduling [2], and job scheduling [3]. Graph coloring is described as vertex coloring, edge coloring, and map coloring. The concept of the chromatic polynomial was introduced as the number of distinct ways of performing map coloring [4]. The chromatic polynomials of many families of graphs have been computed so far [5, 6]. In addition, the computations of the chromatic polynomials of certain graphs using the Mobius inversion theorem were reported by Srinivasa Rao et al. [7].

The fuzzy set theory was introduced by Zadeh [8]. A fuzzy set communicates an element of a given set with a membership value in [0, 1]. The introduction of fuzzy graph theory was given based on the fuzzy set introduced by Kauffman [9]. The traditional fuzzy set cannot be used to completely describe all evidence in the problems where someone wants to know how much nonmembership values. Such a problem got a solution by Atanassov who introduced an intuitionistic fuzzy set (IFS) [10]. IFS is an extension of Zadeh’s set theory and is described by a membership function, a nonmembership function, and a hesitation function [10]. The concept of an intuitionistic fuzzy graph (IFG) was introduced by Atanassov [11]. Atanassov and Shannon developed certain properties of IFGs [12]. And also, Akram and Davvaz discussed more properties of IFGs [13]. Akram et al. presented strong IFGs and intuitionistic fuzzy line graphs [14]. Akram et al. presented an algorithm for computing the sum distance matrix, eccentricity, radius, and diameter of IFG [15]. Electoral systems [16], human cells clustering [17], and water supply systems [18] are some application areas of IFGs. Also, IFG digraph is applied in medical diagnosis, gas pipelines, and decision-making systems [19].

The chromatic polynomials of fuzzy graphs using α-cuts and their algebraic properties were developed by Abebe and Srinivasa Rao Repalle [20]. The coloring of IFG using -cuts (levels) was introduced by Mohideen and Rifayathali [21]. Some properties of IFG by -levels were presented by Akram [22]. To fill the gap in these articles, the authors aimed to find the chromatic polynomial of IFG using -levels, define-fundamental set, and discuss more untouched properties of-level graphs. This paper presents the chromatic polynomial of an IFG using -levels by illustrating it based on -level graphs. In addition, it defines the alpha-beta fundamental set of an IFG. Furthermore, it states and proves some properties of the -level graph and the chromatic polynomial of IFG.

This manuscript is organized as follows: Section 2 is the preliminaries that are essential for understanding the article. Section 3develops some properties of-levels of IFGs and proves wherever verification is required. Section 4 defines the notion of the chromatic polynomial of an IFG using -levels and also develops some related concepts on a chromatic polynomial of an IFG. Section 5 is the summary of the article.

2. Preliminaries

This section defines related concepts such as chromatic polynomial, IFG, and level graph of IFG. In addition, it provides some useful propositions.

Definition 1 (see [20]). The number of distinct ways of attaining a proper vertex coloring of a simple graph with at most colors is called chromatic polynomial of and is denoted by .

Proposition 1 (see [23]). The chromatic polynomial of a simple graph may be found by the formula: , where is the chromatic polynomial of a subgraph of whose one of its edges has been removed, and is the chromatic polynomial of a subgraph of whose one of its edge has been contracted.

Proposition 2 (see [23]). Let be a graph containing nonadjacent vertices and , and let be the graph obtained from the contracting edge . Then, .

Proposition 3 (see [23]). If are pairwise disjoint components of a simple graph whose union is , then its chromatic polynomial is computed as

Definition 2 (see [24]). An intuitionistic fuzzy graph is of the form , where(i) such that and denote the degree of membership and the degree of nonmembership of the element in , respectively, and , for every , (i) where and are such that Satisfy the constraint, for every Where and are the degree of membership and the degree of nonmembership of the element in respectively.

Definition 3 (see [21]). The chromatic number of IFG: is the intuitionistic fuzzy number , where , , , and .

Definition 4. [22]. Let be an IFG. Then, for any , -level graph of is defined as the crisp graph , where , and , .

3. The -Fundamental Set and the Properties of -Level Graph of IFGs

This section defines the -fundamental set and illustrates the -level graph of IFGs. In addition, it states and proves some character of the -level graph of IFGs.

Definition 5. Let be an IFG. If is such that and for each , then is said to be a fundamental set of .

Example 1. Consider an IFG with four intuitionistic fuzzy vertices and five intuitionistic fuzzy edges given in Figure 1.
The fundamental set of an IFG in Figure 1 is  {(0, 1), (0.2, 0.6), (0.3, 0.6), (0.4, 0.5), (0.5, 0.5), (0.8, 0.2)}. To show that the reason why (0.2, 0.5) , consider the levels (0.2, 0.6), (0.2, 0.5), and (0.3, 0.6). Now, let us determine if a level (0.2, 0.5) satisfies the condition in the definition of fundamental set. It is forward that 0.2  0.2, 0.6  0.5, 0.2  0.3 but 0.5  0.6. This shows that (0.2, 0.5) .
The level graphs along with their chromatic number are illustrated in Figure 2.

Figure 1 

Intuitionistic fuzzy graph.

Figure 2 

Illustration on the of the graph in Figure 1 along with their chromatic numbers.

Remark 1. (i)Table 1 contains the vertex set, edge set, and chromatic number of for each in (ii)If there is a vertex with , then -level graph exists(iii) is as contains all the vertices listed in and implies that all the vertices are joined(iv)The chromatic number of an IFG in Figure 1 is given by

3.1. The Properties of-Level Graph of IFGs

Theorem 1. Let be an IFG and and be level graphs of with and . Then,

Proof. Let be an IFG. Suppose and are level graphs of with and . Now, and have vertex sets; and , respectively. To figure out the relation has with , we draw them on the same plane as follows.
Based on Figure 3, is an area of a polygon EFGB and is an area of a polygon ABCD. This shows that is contained in . Thus, .
Similarly, and have the edge sets; and , respectively. For comparison, these sets can be interpreted on the same plane as follows.
Based on Figure 4, is an area of a polygon HLNO and is an area of a polygon HIJK. This indicates that is contained in . Thus, .
Alternate proof: Let and be level graphs of with and . Then,(i)The vertex sets to these levels are and . Now, let . Then, , and since and , it implies . This indicates . Thus, (ii)The edge sets of and are and , respectively.Now, let . Then, and and and , and it implies This shows . Hence, .

Figure 3 

The comparison of with of an IFG.

Figure 4 

The comparison of and of an IFG.

Corollary 1. Let and be level graphs of an IFG, with and . Then,(i)(ii)

Proof. Assume an IFG, . Let and be two-level graphs of with and . Then, by applying Theorem 1: and . Thus, and hold.

Theorem 2. Let and be level graphs of an IFG; with and . Then, is a super graph of .

Proof. Let be an IFG and and be given. Then, by Theorem 1, and . From the fact that if the vertex set and edge set of a certain graph are a subset of a vertex set and edge set of another graph , respectively, then is a super graph of . Thus, is a super graph of .

4. The Chromatic Polynomial of IFG Using -Levels

Here, we define a new idea of the chromatic polynomial of IFG using -levels, and also, we compute the chromatic polynomial of an IFG using -levels for illustration. Furthermore, we state and prove some properties of the chromatic polynomial of IFG using -levels.

Definition 6. Let be IFG and be its fundamental set. Then, the chromatic polynomial of using -level with at most given colors is denoted by and is defined as the chromatic polynomial of , where . That is, for each .

Example 2. Consider the IFG, in Figure 1. All the level graphs of have been put in Figure 2, and by Definition 6, the chromatic polynomial of is the chromatic polynomial of these level graphs. Thus, the chromatic polynomial of is the chromatic polynomial of the level graphs combined in a single equation and is computed as follows:(i)When and , we have , and as , is the chromatic polynomial of . Hence, .(ii)When and , we compute by the addition-contraction method as in Figure 5. Thus, (iii)When and , we have , and it is the chromatic polynomial of . Therefore, .(iv)When and , we obtain and is the chromatic polynomial of . Therefore, .(v)When and , we obtain and is the chromatic polynomial of . Therefore, .(vi)When and , we obtain and is the chromatic polynomial of . Therefore, .In general, the chromatic polynomial of IFG in Figure 1 is summarized in the following equation:

Figure 5 

The computation of .

Remark 2. (i)As increases the degree of the chromatic polynomial, the chromatic number, the number of edges, and the number of vertices decrease.(ii)As decreases the degree of the chromatic polynomial, the chromatic number, the number of edges, and the number of vertices also decrease.

4.1. Properties of the Chromatic Polynomial of IFGs Using -Levels

Theorem 3. Let be IFG on intuitionistic fuzzy vertices and let be -level graph of . If and , then

Proof. Let be an IFG. Then, when and , possesses and .
For every edge in , and . So, every edge in satisfies . In addition to edges in , contains edge(s) correspond to edge(s) labeled of . Therefore, every pair of vertices is joined. , as every vertex in , could satisfy . This implies that and represent the same graph. Hence,

Theorem 4. Let be IFG. If and are intuitionistic fuzzy levels of with and , then

Proof. Assume that IFG. Let and be the level graphs of with and . Then, and . It is obvious to realize that the degree of the chromatic polynomial of a simple graph equals the number of its vertex set. That is, deg( and deg(, and also, since and , (see Corollary 1). Hence, .