An uncertain chromatic number of an uncertain graph based on $\alpha$-cut coloring

Abstract

An uncertain graph is a graph in which the edges are indeterminate and the existence of edges are characterized by belief degrees which are uncertain measures. This paper aims to bring graph coloring and uncertainty theory together. A new approach for uncertain graph coloring based on an $\alpha$-cut of an uncertain graph is introduced in this paper. Firstly, the concept of $\alpha$-cut of uncertain graph is given and some of its properties are explored. By means of $\alpha$-cut coloring, we get an $\alpha$-cut chromatic number and examine some of its properties as well. Then, a fact that every $\alpha$-cut chromatic number may be a chromatic number of an uncertain graph is obtained, and the concept of uncertain chromatic set is introduced. In addition, an uncertain chromatic algorithm is constructed. Finally, a real-life decision making problem is given to illustrate the application of the uncertain chromatic set and the effectiveness of the uncertain chromatic algorithm.

1 Introduction

The vertex coloring problem is the problem of selecting a color to each vertex of a graph such that the colors of adjacent vertices are dissimilar and the number of colors needed is minimized. A lot of researchers have investigated methods on how to color a graph with the minimum number of colors. The vertex coloring problem can be used to model many realistic application problems. In such applications, the vertices of a graph represent items of interest and the vertex coloring problem presents the challenge of grouping the items in as few groups as possible subject to the constraint that incompatible items end up in the different groups. The reader may refer to Brown (1972) for more detail applications of graph coloring. We refer to the classical graph as a crisp graph. The edges and vertices of the crisp graph are all stated definitely. However, the real-life situations which are represented by a graph may be so complex such that adjacency between two vertices cannot be completely determined. Such a system cannot be modeled by a crisp graph. Therefore, we need a tool to represent these indeterminate phenomena in the field of graph theory.

Some researchers studied the indeterminate phenomena by using probability theory. A random variable could be used to represent whether or not two vertices were linked by an edge. The concept of random graph was first proposed by Erdős and Rényi (1959). After that, Gilbert (1959) investigated the probability that the random graph was connected. Additionally, the vertex coloring problems of random graphs were studied by many researchers, such as Sommer (2009) and others.

Zadeh (1965) dealt with the indeterminate phenomena within the framework of fuzzy set theory. Since then, the concept of fuzzy graph was proposed by several authors to handle the fuzzy phenomena in graphs. Muñoz et al. (2005) put forth the method for fuzzy graph coloring in two different ways. In the first approach, the coloring of a fuzzy graph was investigated by using classical coloring on an $\alpha$-cut of a fuzzy graph. In the second approach, the coloring of a fuzzy graph was done by using a coloring function, which depends upon the distance defined between two colors.

However, we need a new tool to investigate the indeterminate phenomena in real-life decision making since it cannot be fully addressed by randomness or fuzziness. For instance, if there is no sample or the sample size is too small, then the probability measure in probability theory is not a legitimate approach to deal with indeterminate phenomena. Consequently, some domain experts would be needed to evaluate the belief degree that each event will occur. Meanwhile, the possibility measure in fuzzy set theory is also not a legitimate approach to deal with indeterminate phenomena. For example, assume that the vertices in a graph represent people and the edges join pairs of friends. Whether two people are friends is not exactly known. Observed information of the friendship for any two people does not exist. Hence, we have $\text{ possibility } \{\text{ the } \text{ people, } \text{ who } \text{ are } \text{ friends, } \text{ are } \text{ exactly } \text{25 }\}=1$ and $\text{ possibility }\{\text{ the } \text{ people, } \text{ who } \text{ are } \text{ not } \text{ friends, } \text{ are } \text{ exactly } \text{25 }\}=1$. This fact is not reasonable within theoretical mathematics. Therefore, the fuzzy set theory is not a suitable tool to handle indeterminate phenomena. In order to handle this difficulty, Liu (2007) introduced uncertain measure within the framework of uncertainty theory.

Uncertainty theory was introduced into graph theory by Gao and Gao (2013). They put forward the concept of an uncertain graph and studied the connectedness index of uncertain graphs. Thereafter, many researchers carried out studies on uncertain graphs. Zhang and Peng (2012) investigated the Euler tour in an uncertain graph and presented the connectedness strength of two vertices in an uncertain graph (Zhang and Peng 2013). Chen et al. (2014) characterized an uncertain minimum weight vertex covering problem in an uncertain network. For more research on uncertain graphs, we may consult Gao (2014, 2016) and Gao et al. (2015).

Recently, Chen and Peng (2014) provided the vertex coloring of an uncertain graph based on maximal uncertain independent vertex set and introduced the concept of uncertain chromatic set of an uncertain graph. However, the steps to obtain the uncertain chromatic set of an uncertain graph based on a maximal uncertain independent vertex set (Chen and Peng 2014) are highly complex and time consuming, especially for an uncertain graph with a large number of vertices and edges. One of the effective methods for solving the coloring problem for a nondeterministic graph is to transform it into classical coloring (Muñoz et al. 2005). Hence, we focus on coloring an uncertain graph via an $\alpha$-cut of an uncertain graph to obtain the uncertain chromatic set. To the best of our knowledge, no one has investigated the uncertain chromatic set of an uncertain graph through $\alpha$-cut coloring before.

The main goal of this paper is to introduce a new approach for coloring an uncertain graph based on an $\alpha$-cut of the uncertain graph. We introduce a concept of an $\alpha$-cut of an uncertain graph, and investigate some of its properties. By means of $\alpha$-cut coloring, we obtain an $\alpha$-cut chromatic number and investigate some properties of the $\alpha$-cut chromatic number. We find that every $\alpha$-cut chromatic number may be a chromatic number of an uncertain graph. Hence, we have an uncertain chromatic set of an uncertain graph. Finally, an uncertain chromatic algorithm is constructed and an illustration for the application of uncertain chromatic set is given. The contributions of this paper are to establish mathematical theory on uncertain graph coloring, to give a new method for uncertain graph coloring which is a useful tool for decision making on uncertain environment, and to develop an algorithm for uncertain graph coloring.

The differences between the proposed studies and the previous works are as follows. On the one hand, Muñoz et al. (2005) defined the concept of $\alpha$-cut of fuzzy graph under the framework of fuzzy set theory. They gave the concept of fuzzy chromatic number of fuzzy graph based on $\alpha$-cut of fuzzy set. Different from the work by Muñoz et al. (2005), the innovation of this research is that we put forward the concept of $\alpha$-cut of uncertain graph based on uncertain measure. After that, the concept of uncertain chromatic set of uncertain graph is constructed via uncertain variables. On the other hand, the differences between the proposed work and the work by Chen and Peng (2014) are as follows. They gave a method to determine an uncertain chromatic set of an uncertain graph through maximal uncertain independent vertex sets. The contribution of our method is that we define the uncertain chromatic set of an uncertain graph through $\alpha$-cut coloring, which is a classical coloring. The important step in our method is in finding the $\alpha$-cut chromatic number of an uncertain graph. This step can be determined via algorithms for the chromatic number of a crisp graph. Therefore, the advantage of our proposed method is that the steps to determine the uncertain chromatic set become easier and simpler than the steps given by Chen and Peng (2014), especially for uncertain graph with the large number of vertices and edges.

The rest of this paper is organized as follows. Section 2 contains brief summaries of uncertainty theory, classical graph theory, and uncertain graph theory. In Sect. 3, we introduce the concept of an $\alpha$-cut of an uncertain graph and study some characteristics of the $\alpha$-cut and the $\alpha$-cut chromatic number. Our main results are discussed in Sect. 4. An illustration for the uncertain chromatic set of an uncertain graph is indicated in Sect. 5. Section 6 establishes the innovations of the proposed work and provides comparisons to the existing work. Finally, conclusions are presented in Sect. 7.

2 Preliminaries

This section contains brief summaries of uncertainty theory, classical graph theory, uncertain graph theory, and the concept of uncertain chromatic set based on uncertain independent vertex set.

2.1 Uncertainty theory

Uncertainty theory was initialized by Liu (2007) and refined by Liu (2010) to model human uncertainty. Nowadays, it has become a branch of axiomatic mathematics for modeling belief degrees and has been applied to other areas, such as uncertain programming (Chen et al. 2014), uncertain differential equation (Ji and Zhou 2015), uncertain finance (Yao 2015), uncertain contract theory (Wu et al. 2014; Yang et al. 2016), uncertain process (Liu 2014; Yao 2015), and so on. In this subsection, we recall some of standard facts on uncertainty theory.

Let $\Gamma$ be a nonempty set and $\mathcal{L}$ a $\sigma$-algebra over $\Gamma$. A pair $(\Gamma ,\mathcal{L})$ is called a measurable space and each element $\Lambda$ in $\mathcal{L}$ is called an event. A function $\mathcal {M}:\mathcal{L}\rightarrow [0,1]$ is said to be an uncertain measure if it satisfies the following three axioms (Liu 2007):

• Axiom I (Normality) $\mathcal {M}\{\Gamma \}=1$ for the universal set $\Gamma$;

• Axiom II (Duality) $\mathcal {M}\{\Lambda \}+\mathcal {M}\{\Lambda ^{c}\}=1$ for any event $\Lambda$;

• Axiom III (Subadditivity) For every countable sequence of events $\Lambda _{1},\Lambda _{2},\ldots ,$ we have

  $$\begin{aligned} \mathcal {M}\left\{ \bigcup _{i=1}^{\infty }\Lambda _{i}\right\} \le \sum _{i=1}^{\infty }\mathcal {M}\{\Lambda _{i}\}. \end{aligned}$$

For example, let $\Gamma =\{\gamma _{1},\gamma _{2},\gamma _{3}\}$. The $\sigma$-algebra $\mathcal L$ consists of 8 events. Define a function $\mathcal {M}$ as follows: $\mathcal {M}\{\gamma _{1}\}=0.4, \mathcal {M}\{\gamma _{2}\}=0.5, \mathcal {M}\{\gamma _{3}\}=0.3, \mathcal {M}\{\gamma _{1},\gamma _{2}\}=0.7, \mathcal {M}\{\gamma _{1},\gamma _{3}\}=0.5, \mathcal {M}\{\gamma _{2},\gamma _{3}\}=0.6, \mathcal {M}\{\emptyset \}=0$, and $\mathcal {M}\{\Gamma \}=1$. It can be proved that $\mathcal {M}$ is an uncertain measure.

The triplet $(\Gamma ,\mathcal{L},\mathcal {M})$ is called an uncertainty space. In order to provide the operational law, Liu (2009) proposed the following product axiom.

• Axiom IV (Product) Let $(\Gamma _{k},\mathcal{L}_{k},\mathcal {M}_{k})$ be uncertainty spaces for $k=1, 2, \ldots$ The product of uncertain measure $\mathcal {M}$ is an uncertain measure satisfying

  $$\begin{aligned} \mathcal {M}\left\{ \prod _{k=1}^{\infty }\Lambda _{k}\right\} = \bigwedge _{k=1}^{\infty }\mathcal {M}_{k}\{\Lambda _{k}\}, \end{aligned}$$

  where $\Lambda _{k}$ are arbitrarily events from $\mathcal{L}_{k}$ for $k=1, 2, \ldots ,$ respectively.

An uncertain variable is a function $\xi$ from an uncertainty space $(\Gamma ,\mathcal{L},\mathcal {M})$ to the set of real numbers such that $\{\xi \in B\}=\{\gamma \in \Gamma | \xi (\gamma )\in B\}$ is an event for any Borel set B of real numbers. For example, let $(\Gamma ,\mathcal{L},\mathcal {M})$ be an uncertainty space where $\Gamma =\{\gamma _{1},\gamma _{2}\}$ with $\mathcal {M}\{\gamma _{1}\}=\mathcal {M}\{\gamma _{2}\}=0.5$. The function

$$\begin{aligned} \xi (\gamma )=\left\{ \begin{array}{cl} 1, &{}\quad \text{ if }\quad ~\gamma =\gamma _{1}\\ 0, &{}\quad \text{ if }\quad ~\gamma =\gamma _{2}\\ \end{array}\right. \end{aligned}$$

is an uncertain variable.

In order to describe an uncertain variable $\xi$ in practice, Liu (2007) suggested the concept of an uncertainty distribution as follows. The uncertainty distribution $\Phi (x): \mathfrak {R}\rightarrow [0,1]$ of an uncertain variable $\xi$ is defined by

$$\begin{aligned} \Phi (x)=\mathcal {M}\left\{ \gamma \in \Gamma | \xi (\gamma )\le x\right\} ,\quad \forall x\in \mathfrak {R}. \end{aligned}$$

For simplicity, the uncertainty distribution $\Phi$ can be denoted as

$$\begin{aligned} \Phi (x)=\mathcal {M}\left\{ \xi \le x\right\} ,\quad \forall x\in \mathfrak {R}. \end{aligned}$$

The inverse function $\Phi ^{-1}$ is called the inverse uncertainty distribution of $\xi$.

The concept of independent uncertain variables was introduced by Liu (2009) as follows. The uncertain variables $\xi _{1},\xi _{2}, \ldots ,\xi _{n}$ are called independent if

$$\begin{aligned} \mathcal {M}\left\{ \bigcap _{i=1}^{n}(\xi _{i}\in B_{i})\right\} = \bigwedge _{i=1}^{n}\mathcal {M}\{\xi _{i}\in B_{i}\} \end{aligned}$$

for any Borel sets $B_{1}, B_{2}, \ldots , B_{n}$ of real numbers.

2.2 Classical graph theory

In this subsection, the definition of graph and basic terminologies of graph theory are reviewed in a more general setting. We assume that every graph is an undirected, simple, and finite graph.

Definition 2.1

(Bondy and Murty 1976) A graph G is an ordered triple $(V,E,\psi _{G})$ consisting of a nonempty vertex set V(G), an edge set E(G) and an incidence function $\psi _{G}$ that associates with each edge of G an unordered pair of vertices of G.

The number of vertices in the graph $G=(V,E,\psi _{G})$ is often called the order of G. If e is an edge, and u and v are vertices such that $\psi _{G}(e)=(u,v)$, then the vertices u and v are called adjacent. A set $I\subseteq V$ is said to be an independent vertex set if $(u,v)\not \in E(G)$ for all $u,v\in I$.

Given a graph $G=(V,E,\psi _{G})$. A k-coloring of the graph G can be defined through two approaches. In the first approach, the k-coloring of the graph G is defined as a mapping from the vertex set V into the set of colors $\{1,2, \ldots ,k\}$ such that two adjacent vertices are assigned with different colors. In the second approach, the k-coloring of the graph G is defined as a partition of V into k-independent vertex sets $V_{1},V_{2}, \ldots ,V_{k}$ such that $\displaystyle \bigcup _{i=1}^{k}V_{i}=\displaystyle V$ where the subsets $V_{i}$ are nonempty, and $V_{i}\cap V_{j}=\emptyset$ for $i\ne j$. The minimum number k needed in the k-coloring of G, is called the chromatic number of G, denoted by $\chi (G)$.

2.3 Uncertain graph

Gao and Gao (2013) employed uncertainty theory into graph theory and introduced an uncertain graph as in Definition 2.2.

Definition 2.2

(Gao and Gao 2013) An uncertain graph, denoted by $\check{G}=(V,E,\xi )$, is a triple consisting of a vertex set $V(\check{G})$, an edge set $E(\check{G})$ and an indicator function $\xi$.

The uncertain graph consists of vertices which are deterministic and edges which are indeterminate. The existence of edges represented by belief degrees which are uncertain measures. A Boolean uncertain variable $\xi$, which is an indicator function, is needed to represent the existence of a corresponding edge. If the edge $(v_{i},v_{j})$ exists, then $\xi _{ij}=1$; otherwise, $\xi _{ij}=0$. For convenience, the uncertain graph $\check{G}=(V,E,\xi )$ can be denoted by $\check{G}$.

Another way to describe an uncertain graph is by using an uncertain adjacency matrix as follows:

$$\begin{aligned} X=\left( \begin{array}{cccc} \alpha _{11}&{}\quad \alpha _{12}&{}\quad \ldots &{}\quad \alpha _{1n}\\ \alpha _{21}&{}\quad \alpha _{22}&{}\quad \ldots &{}\quad \alpha _{2n}\\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ \alpha _{n1}&{}\quad \alpha _{n2}&{}\quad \ldots &{}\quad \alpha _{nn} \end{array}\right) , \end{aligned}$$

where $\alpha _{ij}$ is the uncertain measure that the edge between the vertices $v_{i}$ and $v_{j}$ exists for $i,j=1,2, \ldots ,n$, respectively. If there is an edge between the vertices $v_{i}$ and $v_{j}$, then $\mathcal {M}\{\xi _{ij}=1\}=\alpha _{ij}$. Otherwise, $\mathcal {M}\{\xi _{ij}=0\}=1-\alpha _{ij}$.

The concept of underlying graph of an uncertain graph was provided by Zhang and Peng (2013) as stated on Definition 2.3.

Definition 2.3

(Zhang and Peng 2013) Let $\check{G}=(V,E,\xi )$ be an uncertain graph with the edge set $E(\check{G})=\{\xi _{1}, \xi _{2}, \ldots , \xi _{n}\}.$ The underlying graph of $\check{G}$, denoted by $G^{*}$, is defined as a graph which is obtained from $\check{G}$ by replacing the uncertain measure $\mathcal {M}\{\xi _{ij}=1\}=1$ for each pair $(v_{i},v_{j})$, where $\xi _{ij}=1$.

2.4 The uncertain chromatic set based on uncertain independent vertex set

In this subsection, we summarize the relevant material without proof on the uncertain chromatic set based on maximal uncertain independent vertex sets, which was given by Chen and Peng (2014).

Definition 2.4

(Chen and Peng 2014) Let $\check{G}=(V,E,\xi )$ be an uncertain graph. A subset of vertices $X\subseteq V$ is called an uncertain independent vertex set with independence degree

$$\begin{aligned} \displaystyle I(X)=1-\max \{\mathcal {M}\{\xi _{ij}=1\}|v_{i},v_{j}\in X\}. \end{aligned}$$

(1)

The independence degree of X is the belief degree that X is an uncertain independent vertex set of uncertain graph $\check{G}$. The concept of a maximal uncertain independent vertex set was defined by Chen and Peng (2014) as follows.

Definition 2.5

(Chen and Peng 2014) Assume that $\check{G}=(V,E,\xi )$ is an uncertain graph. A subset of vertices $X\subseteq V$ with independence degree I(X) is said to be a maximal uncertain independent vertex set, if $I(X^{\prime })<I(X)$ for any uncertain independent vertex set $X'\supset X.$

In order to define the uncertain chromatic set of an uncertain graph, Chen and Peng (2014) presented the concept of separation degree as follows.

Definition 2.6

(Chen and Peng 2014) Let $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices. Let ${\mathcal {A}}$ be the family of all maximal uncertain independent vertex sets of $\check{G}$. For each $k\in \{1, 2, \ldots ,n\},$ the value

$$\begin{aligned} S(k)=min \{I(X_{1}),\quad I(X_{2}),\ldots ,I(X_{k})|X_{i}\in {\mathcal {A}},\quad i=1,2,\ldots ,k\} \end{aligned}$$

is called the separation degree of the uncertain graph $\check{G}$ which is colored by k colors.

The separation degree S(k) is the belief degree that the uncertain graph $\check{G}$ can be colored by k colors.

Definition 2.7

(Chen and Peng 2014) Let $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices. A set $\chi (\check{G})=\{\left( k,S_{\chi }(k)\right) \mid k=1,2,\ldots ,n\}$ is said to be an uncertain chromatic set of the uncertain graph $\check{G}$ if $S_{\chi }(k)$ is the maximum separation degree of the uncertain graph $\check{G}$ with k colors, i.e.,

$$\begin{aligned} S_{\chi }(k)\ge S(k) \end{aligned}$$

for any separation degree S(k) of k-subsets of ${\mathcal {A}}$ and for $k=1,2,\ldots ,n$.

In the following section, we present another approach for determining the uncertain chromatic set of an uncertain graph. The new approach is based on $\alpha$-cut coloring of an uncertain graph. We will propose the concept of an $\alpha$-cut of an uncertain graph in Sect. 3.

3 Coloring an uncertain graph via its $\alpha$-cut

This section will introduce the concept of an $\alpha$-cut of an uncertain graph and investigate several properties of the new concept.

Definition 3.1

Let $\alpha \in [0,1]$. An $\alpha$-cut of uncertain graph $\check{G}=(V,E,\xi )$ is a crisp graph $G^{\alpha }=(V,E^{\alpha })$, where $E^{\alpha }=\{(v_{i},v_{j})|v_{i},v_{j}\in V, \mathcal {M}\{\xi _{ij}= 1\}\ge \alpha \}$.

An example that illustrates the concept of the $\alpha$-cut of an uncertain graph is given as follows.

Example 3.2

Consider the uncertain graph $\check{G}=(V,E,\xi )$ in Fig. 1. There are five vertices in the uncertain graph $\check{G}$ and its edges exist with the corresponding belief degrees 0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, and 1, respectively.

Fig. 1

Uncertain graph $\check{G}=(V,E,\xi )$

The $\alpha$-cut $G^{\alpha }$ for $0.1<\alpha \le 0.3$ and $0.5<\alpha \le 0.6$ are given in Figs. 2 and 3, respectively. For more detail, the edge sets of the $\alpha$-cut $G^{\alpha }=(V,E^{\alpha })$ for $\alpha \in [0,1]$ are summarized in Table 1.

Fig. 2

The $\alpha$-cut $G^{\alpha }$ for $0.1<\alpha \le 0.3$

Fig. 3

The $\alpha$-cut $G^{\alpha }$ for $0.5<\alpha \le 0.6$

Further, some properties of the $\alpha$-cut of an uncertain graph are investigated as follows.

Theorem 3.3

If $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices and $G^{*}$ be the underlying graph of $\check{G}$, then the $\alpha$-cut $G^{\alpha }=G^{*}$ for all $0<\alpha \le \min \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}.$

Proof

Let $\alpha _{r}=\min \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}$, and $0<\alpha \le \alpha _{r}$. The edge set $E^{\alpha }=\{(v_{i},v_{j})|v_{i},v_{j}\in V, \alpha \le \mathcal {M}\{\xi _{ij}= 1\}<\alpha _{r}\}\cup \{(v_{i},v_{j})|v_{i},v_{j}\in V, \mathcal {M}\{\xi _{ij}= 1\}\ge \alpha _{r}\}$. Since $\alpha _{r}=\min \{\mathcal {M}\{\xi _{ij}=1\}\}$, we get $\{(v_{i},v_{j})|v_{i},v_{j}\in V, \alpha \le \mathcal {M}\{\xi _{ij}= 1\}<\alpha _{r}\}=\emptyset$. Thus, $E^{\alpha }=\{(v_{i},v_{j})|v_{i},v_{j}\in V, \mathcal {M}\{\xi _{ij}= 1\}\ge \alpha _{r}\}$. It means that $E^{\alpha }$ contains all of pairs $(v_{i},v_{j})$ in $\check{G}$ where $\xi _{ij}=1$, and $\mathcal {M}\{\xi _{ij}= 1\}>\min \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}$.

We consider that the underlying graph $G^{*}$ is obtained from the uncertain graph $\check{G}$ by replacing the uncertain measure for each pair $(v_{i},v_{j})$ where $\xi _{ij}=1$, by $\mathcal {M}\{\xi _{ij}= 1\}=1$ for $i,j=1,2,\ldots ,n$. Therefore, we get each edge $(v_{i},v_{j})\in E^{\alpha }$ in $G^{\alpha }$ is contained in $E^{*}$ of $G^{*}$. Thus, $E^{\alpha }=E^{*}$ and $G^{\alpha }=G^{*}$ for all $0<\alpha \le \min \left\{ \mathcal {M}\{\xi _{ij}=1\}\right\}$. $\square$

Lemma 3.4

If $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices and $\max \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}<1$, then the $\alpha$-cut $G^{\alpha }$ is an isolated graph for all $\max \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}<\alpha \le 1.$

Table 1 List of the $\alpha$-cut $G^{\alpha }=(V,E^{\alpha })$ with different cut levels

Proof

Since $1\ge \alpha > \max \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}$, $E^{\alpha }=\emptyset$. In other words, the $\alpha$-cut $G^{\alpha }=(V,E^{\alpha })$ is a graph without edges (isolated graph).$\square$

Each $\alpha$-cut of an uncertain graph is a crisp graph. We call the chromatic number of an $\alpha$-cut of an uncertain graph as $\alpha$-cut chromatic number, denoted by $\chi ^{\alpha }$. Hence, coloring the uncertain graph $\check{G}$ is transformed into classical coloring via the $\alpha$-cut of $\check{G}$.

An example is given below to illustrate the relationship between the value $\alpha$ and the $\alpha$-cut chromatic number of the uncertain graph $\check{G}$.

Example 3.5

Let $A=\{0,0.1,0.3,0.4,0.5,0.6,0.7,0.8,1\}$ be the set of the belief degrees of all edges in the uncertain graph $\check{G}=(V,E,\xi )$ given in Fig. 1. The $\alpha$-cut chromatic numbers $\chi ^{\alpha }$ of $\check{G}$ are presented in Table 2 for all $\alpha \in [0,1]$.

Table 2 List of the $\alpha$-cut chromatic numbers $\chi ^{\alpha }$

The following theorems provide the properties of the $\alpha$-chromatic number. These results will be needed in Sect. 4.

Theorem 3.6

Let $\check{G}=(V,E,\xi )$ be an uncertain graph with the vertex set $V=\{v_{1},v_{2},\ldots ,v_{n}\}$. If $\alpha =0,$ then the $\alpha$-cut chromatic number $\chi ^{\alpha }=n$.

Proof

Since $\alpha =0$, $E^{\alpha }$ consists of all pairs of vertices $(v_{i},v_{j})$ for all $i,j=1,2,\ldots ,n$. In other words, each pair $(v_{i},v_{j})$ of vertices in $G^{\alpha }$ is connected by an edge. Therefore, $\chi ^{\alpha }=n$. $\square$

Theorem 3.7

The value $\alpha \le \beta$ if and only if $\chi ^{\alpha }\ge \chi ^{\beta }.$

Proof

Let $\alpha \le \beta$. It is obvious that $G^{\alpha }\supseteq G^{\beta }$. Thus, the chromatic number $\chi ^{\alpha }\ge \chi ^{\beta }$. Otherwise, let $\chi ^{\alpha }\ge \chi ^{\beta }$. It is obvious that $G^{\alpha }\supseteq G^{\beta }$. It means that $E^{\alpha }\supseteq E^{\beta }$. Based on Definition 3.1, we obtain $E^{\alpha }=\{(v_{i},v_{j})|v_{i},v_{j}\in V, \alpha \le \mathcal {M}\{\xi _{ij}= 1\}<\beta \}\cup \{(v_{i},v_{j})|\mathcal {M}\{\xi _{ij}= 1\}\ge \beta \}$. Thus, $\alpha \le \beta$. $\square$

Theorem 3.7 shows that the $\alpha$-cut chromatic number is a decreasing function of $\alpha$.

Theorem 3.8

Let $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices. If $G^{*}$ is the underlying graph of the uncertain graph $\check{G}$ and $G^{*}$ is not a complete graph, then the chromatic number

$$\begin{aligned} \chi (G^{*})=\max \{\chi ^{\alpha }| \alpha \in (0,1]\}. \end{aligned}$$

Proof

According to Theorem 3.3, $G^{*}=G^{\alpha }$ for all $0<\alpha \le \min \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}$. Let $\alpha _{r}=\min \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}$. First, we prove that

$$\begin{aligned} G^{\alpha }=G^{\alpha _{r}}\quad \text{ for } \text{ all }~0<\alpha < \alpha _{r}. \end{aligned}$$

(2)

Let $0<\alpha <\alpha _{r}$. Based on Definition 3.1, the edge set $E^{\alpha }$ can be rewritten as $E^{\alpha }=\{(v_{i},v_{j})| v_{i},v_{j}\in V, \alpha \le \mathcal {M}\{\xi _{ij}=1\}<\alpha _{r}\}\cup \{(v_{i},v_{j})| v_{i},v_{j}\in V, \mathcal {M}\{\xi _{ij}=1\}\ge \alpha _{r}\}$. Since $\alpha _{r}=\min \{\mathcal {M}\{\xi _{ij}=1\}|i,j=1,2,\ldots ,n\}$, we have the following result: $\{(v_{i},v_{j})| v_{i},v_{j}\in V, \alpha \le \mathcal {M}\{\xi _{ij}=1\}<\alpha _{r}\}=\emptyset$. Thus, $E^{\alpha }=\{(v_{i},v_{j})| v_{i},v_{j}\in ~V, \mathcal {M}\{\xi _{ij}=1\}\ge \alpha _{r}\}=E^{\alpha _{r}}$, and $G^{\alpha }=G^{\alpha _{r}}$ for all $0<\alpha <\alpha _{r}$. Therefore, $\chi (G^{\alpha })=\chi (G^{\alpha _{r}})$ for all $0<\alpha \le \alpha _{r}$.

Second, it follows from Theorem 3.7 that $\chi ^{\alpha }<\chi ^{\alpha _{r}}$ for all $\alpha \in (0,1]$ where $\alpha >\alpha _{r}$. Thus,

$$\begin{aligned} \chi ^{\alpha _{r}}=\max \{\chi ^{\alpha }|\alpha \in (0,1]\}. \end{aligned}$$

(3)

Based on Eqs. (2) and (3), we have $\chi (G^{*})=\chi ^{\alpha _{r}}=\max \{\chi ^{\alpha }| \alpha \in (0,1]\}.$ $\square$

In Sect. 4, the concept of an uncertain chromatic set based on $\alpha$-cut coloring is proposed for the first time.

4 An uncertain chromatic set based on $\alpha$-cut coloring

If we color an uncertain graph $\check{G}=(V,E,\xi )$ with n vertices through coloring the $\alpha$-cut of $\check{G},$ then we have $\alpha$-cut chromatic number $k\in \{1,2,\ldots ,n\}$. It means that the uncertain graph $\check{G}$ with n vertices may be colored in an arbitrary number k colors.

One question naturally arises: what is the chromatic number of the uncertain graph $\check{G}$? Every $\alpha$-cut chromatic number $k\in \{1,2,\ldots ,n\}$ may be a chromatic number of the uncertain graph $\check{G}$. Hence, any $\alpha$-cut chromatic number becomes an uncertain chromatic number for an uncertain graph. More precisely speaking, we have an uncertain event $\Lambda _{k}$ that corresponds to the proposition “the chromatic number of $\check{G}$ is approximately k”. In the next section, the concept of uncertain chromatic set which is determined via $\alpha$-cut coloring is introduced.

4.1 The concept of uncertain chromatic set

Let us suppose $\Gamma$ is a universal set which consists of $\alpha$-cut chromatic numbers of the uncertain graph $\check{G}=(V,E,\xi )$ for all $\alpha \in [0,1]$. Further, let $\Lambda$ be a proper nonempty subset of $\Gamma$ and $\mathcal {L}=\{\emptyset ,\Lambda ,\Lambda ^{c},\Gamma \}$ a $\sigma$-algebra over $\Gamma$.

Let $\Lambda _{k} \in \mathcal {L}$ be an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately k”. Then it may be represented by $\Lambda _{k}=\{k\}$. Let $\Lambda$ be an uncertain event that corresponds to the proposition “the chromatic number of $\check{G}$ may be in $\Lambda$”. We give a belief degree $\mathcal {M}\{\Lambda \}$ to represent the belief degree of event $\Lambda$. In this paper, the belief degree $\mathcal {M}$ is determined via $\alpha$-cut coloring.

Definition 4.1

Let $\check{G}=(V,E,\xi )$ be an uncertain graph. The belief degrees $\mathcal {M}\{\Lambda \}$ and $\mathcal {M}\{\Lambda ^{c}\}$ are defined as follows:

$$\begin{aligned} \mathcal {M}\{\Lambda \}= & {} 1-\inf \{\alpha | \chi ^{\alpha }\in \Lambda \},\nonumber \\ \mathcal {M}\{\Lambda ^{c}\}= & {} \inf \{\alpha | \chi ^{\alpha }\in \Lambda \}. \end{aligned}$$

(4)

Based on Definition 4.1, the belief degree $\mathcal {M}\{\Lambda _{k}\}$ is defined as follows:

$$\begin{aligned} \displaystyle \mathcal {M}\{\Lambda _{k}\}=1-\inf \{\alpha |\alpha \in [0,1], \chi ^{\alpha }=k\} \quad \text{ and }\quad \mathcal {M}\{\Lambda _{k}^{c}\}=\inf \{\alpha |\alpha \in [0,1], \chi ^{\alpha }=k\}. \end{aligned}$$

Further, we prove that the belief degree $\mathcal {M}$ as discussed in Definition 4.1 is an uncertain measure on the $\sigma$-algebra $\mathcal {L}$.

Theorem 4.2

The belief degree $\mathcal {M}$ defined in (4) is an uncertain measure.

Proof

We will prove that the belief degree $\mathcal {M}$ defined in (4) satisfies the three axioms of uncertainty theory.

• 1. First, we prove that it meets the normality axiom. Based on Definition 4.1, the value $\inf \{\alpha |\alpha \in [0,1], \chi ^{\alpha }\in \Gamma \}=0$. Therefore, $\mathcal {M}\{\Gamma \}=1-0=1$.

• 2. It follows from Definition 4.1 that $\mathcal {M}\{\Lambda \}+\mathcal {M}\{\Lambda ^{c}\}=1$ for all $\Lambda \subseteq \Gamma$. Hence, it meets the duality axiom.

• 3. It is obvious that

  $$\begin{aligned} \displaystyle \mathcal {M}\left\{ \bigcup _{i=1}^{t}\Lambda _{i}\right\} \displaystyle= & {} 1-\inf \{\alpha | \chi ^{\alpha }\in \{\Lambda _{1}\cup \Lambda _{2}\cup \ldots \cup \Lambda _{t}\}\} \le [1-\inf \{\alpha | \chi ^{\alpha }\in \Lambda _{1}\}] \\&+\,[1-\inf \{\alpha | \chi ^{\alpha }\in \Lambda _{2}\}]+\cdots \\&+\,[1-\inf \{\alpha | \chi ^{\alpha }\in \Lambda _{t}\}]=\displaystyle \sum _{i=1}^{t}\mathcal {M}\{ \Lambda _{i}\}\displaystyle . \end{aligned}$$

Hence, it meets the subadditivity axiom. Thus, $\mathcal {M}$ is an uncertain measure. $\square$

Finally, we have an uncertainty space $(\Gamma ,\mathcal {L},\mathcal {M})$. For the sake of convenience, an indicator function $\pi _{k}$, which is a Boolean uncertain variable, can be used to indicate the existence of the uncertain event $\Lambda _{k}\in \mathcal {L}$ corresponds to the proposition that “the chromatic number of the uncertain graph $\check{G}$ is approximately k”. If the event $\Lambda _{k}$ exists, then $\pi _{k}=1$, and otherwise $\pi _{k}=0$. Further, the concept of the uncertain chromatic set of an uncertain graph is defined as set of Boolean uncertain variables.

Definition 4.3

Let $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices. Assume that $\pi _{k}$, $k=1,2,\ldots ,n$ are independent Boolean uncertain variables. Let $\Lambda _{k}$ be an uncertain event corresponds to the proposition that “the chromatic number of the uncertain graph $\check{G}$ is approximately k”. The uncertain chromatic set of uncertain graph $\check{G}$ is defined as a set $\rho (\check{G})=\{(\pi _{k},\mathcal {M}\{\pi _{k}=1\})|k=1,2,\ldots ,n\}$, where the uncertain measures $\mathcal {M}\{\pi _{k}=1\}=1-\inf \{\alpha | \chi ^{\alpha }=k\}=\beta _{k}$ and $\mathcal {M}\{\pi _{k}=0\}=1-\beta _{k}$.

Let $G^{*}$ be the underlying graph of uncertain graph $\check{G}$. If a Boolean uncertain variable $\pi _{k}$ has the uncertain measure $\mathcal {M}\{\pi _{k}=1\}=1$ in the uncertain chromatic set $\rho (\check{G})$, then k is a crisp chromatic number of underlying graph $G^{*}$. Thus, the concept of the uncertain chromatic set is consistent with the crisp chromatic number.

Next, we prove the monotonicity property of the uncertain measure $\mathcal {M}$, as mentioned in Definition 4.1.

Theorem 4.4

Let $\check{G}=(V,E,\xi )$ be an uncertain graph, $G^{*}$ the underlying graph of the uncertain graph $\check{G}$ and k the chromatic number of $G^{*}$. Let $\Lambda _{i}$ an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately i”, $\Lambda _{j}$ an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately j”, $\Lambda$ an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ may be in $\Lambda$”, and $\Omega$ an uncertain even corresponds to the proposition that “the chromatic number of $\check{G}$ may be in $\Omega$”. If $i\le j\le k$, then $\mathcal {M}\{\Lambda _{i}\}\le \mathcal {M}\{\Lambda _{j}\}$. Further, if $\Lambda \subset \Omega$, then $\mathcal {M}\{\Lambda \}\le \mathcal {M}\{\Omega \}$ for $\Lambda , \Omega \in \mathcal {L}$.

Proof

Let $A=\{\alpha \in [0,1]|\chi ^{\alpha }=i\}$ and $B=\{\beta \in [0,1]|\chi ^{\beta }=j\}$. We have $i\le j\le k$. According to Theorem 3.7, we have $\alpha \ge \beta$ for all $\alpha \in A$ and $\beta \in B$. Hence, $\inf \{\alpha \}\ge \inf \{\beta \}$. Therefore, $1- \inf \{\alpha | \chi ^{\alpha }=i\} \le 1- \inf \{\beta |\chi ^{\beta }=j\}$. It is obvious that $\mathcal {M}\{\Lambda _{i}\}\le \mathcal {M}\{\Lambda _{j}\}$. Further, let $\Lambda , \Omega \in \mathcal {L}$ where $\Lambda \subset \Omega$. Hence, $\{\alpha | \chi ^{\alpha }\in \Lambda \}\subseteq \{\beta | \chi ^{\beta }\in \Omega \}$. Based on the properties of infimum, we have $\inf \{\alpha | \chi ^{\alpha }\in \Lambda \}\ge \inf \{\beta | \chi ^{\beta }\in \Omega \}$. Therefore, $1-\inf \{\alpha | \chi ^{\alpha }\in \Lambda \}\le 1-\inf \{\beta | \chi ^{\beta }\in \Omega \}$. Thus, $\mathcal {M}\{\Lambda \}\le \mathcal {M}\{\Omega \}$. $\square$

Theorem 4.5

Let $\check{G}=(V,E,\xi )$ be an uncertain graph with n vertices, and k the chromatic number of the underlying graph $G^{*}$. Let $\Lambda _{i}$ be an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately i”, and $\Lambda _{j}$ an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately j” with the belief degrees $\mathcal {M}\{\Lambda _{i}\}$ and $\mathcal {M}\{\Lambda _{j}\}$, respectively. If $k\le i\le j\le n$, then $\mathcal {M}\{\Lambda _{i}\}=\mathcal {M}\{\Lambda _{j}\}=1$.

Proof

Let $\Lambda _{k}$ be an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately k”. It follows from Remark 4.1.2 that $\mathcal {M}\{\Lambda _{k}\}=1$. Let $\Lambda _{n}$ be an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately n”. It follows from Remark 4.1.3 that $\mathcal {M}\{\Lambda _{n}\}=1$. We have $k\le i\le j\le n$. According to Theorem 4.4, we obtain $\mathcal {M}\{\Lambda _{k}\}=1\le \mathcal {M}\{\Lambda _{i}\} \le \mathcal {M}\{\Lambda _{j}\}\le \mathcal {M}\{\Lambda _{n}\}=1$. Thus, $\mathcal {M}\{\Lambda _{i}\}=\mathcal {M}\{\Lambda _{j}\}=1$. $\square$

Theorem 4.6

Let $\Lambda _{1}$ be an uncertain event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately 1”. If $\max \{\mathcal {M}\{\xi _{ij}=1\}|v_{i},v_{j}\in V\}<1$, then the belief degree of the event $\Lambda _{1}$ is $\mathcal {M}\{\Lambda _{1}\}>0.$

Proof

Let $\alpha _{r}=\max \{\mathcal {M}\{\xi _{ij}=1\}|v_{i},v_{j}\in V\}<1$. Therefore, $\chi ^{\alpha }=1$ for all $\alpha _{r}<\alpha <1$. Hence, $0<\inf \{\alpha | \chi ^{\alpha }=1\}<1$. Thus, $\mathcal {M}\{\Lambda _{1}\}=1-\inf \{\alpha |\chi ^{\alpha }=1\}>0.$ $\square$

Based on the properties of $\alpha$-cut coloring in uncertain graph, we propose an algorithm to determine the uncertain chromatic set of an uncertain graph, which is called uncertain chromatic algorithm.

4.2 Uncertain chromatic algorithm

Let $\check{G}=(V,E,\xi )$ be an uncertain graph with $V = \{v_{1}, v_{2},\ldots ,v_{n}\}$. The uncertain graph $\check{G}$ is a simple and undirected graph. Hence, $\alpha _{ii}=0$ for $i=1,2,\ldots ,n$ and $\alpha _{ij}=\alpha _{ji}$ for any i and j. For the sake of simplicity, we remove the edges $\xi _{ij}$ with $\mathcal {M}\{\xi _{ij}=1\}=0$. Let $A=\{\alpha _{1},\alpha _{2},\ldots ,\alpha _{m}\}$ be the set of the belief degrees of all edges in $\check{G}$. Let $\Lambda _{k}\in \mathcal {L}$ be an event corresponds to the proposition that “the chromatic number of $\check{G}$ is approximately k” and $\pi _{k}$ is a Boolean uncertain variable that represents the existence of uncertain event $\Lambda _{k}$.

• Step 1 Initialize: for $\alpha =\alpha _{0}=0$, and $\chi ^{\alpha }=n$.

• Step 2 For $\alpha =\alpha _{1}>0$: determine the $\alpha$-cut $G^{\alpha }=(V,E^{\alpha })$, $E^{\alpha }=\{v_{i},v_{j}\in V|\mathcal {M}\{\xi _{ij}=1\}\ge \alpha \}$.

• Step 3 Find the $\alpha$-cut chromatic number $\chi ^{\alpha }$. Set $\alpha =\alpha _{i+1}, i=1,2,\ldots ,m-1$. If $\alpha \le \alpha _{m}$, then go to Step 2. Otherwise, go to Step 4.

• Step 4 Set $T_{k}=\{\alpha \in [0,1]|\chi ^{\alpha }=k\}$ and $\beta _{k}=1-\inf \{\alpha |\alpha \in T_{k}\}$. Put $\mathcal {M}\{\pi _{k}=1\}=\beta _{k}$, and $\mathcal {M}\{\pi _{k}=0\}=1-\beta _{k}$. If $T_{k}=\emptyset$, then $\mathcal {M}\{\pi _{k}=1\}=0$.

• Step 5 For $k=1,2,\ldots ,n$: the uncertain chromatic set is $\rho (\check{G})=\{(\pi _{k},\mathcal {M}\{\pi _{k}=1\})\}$.

In Step 3, coloring of the uncertain graph $\check{G}$ is transformed into the classical coloring by means of its $\alpha$-cut. Hence, the uncertain chromatic algorithm proposed in this paper is simpler than the algorithm based on the maximum uncertain independent vertex set (Chen and Peng 2014).

Example 4.7

Consider the uncertain graph $\check{G}=(V,E,\xi )$ given in Fig. 1. There are five vertices and let $A=\{0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 1\}$ be the set of belief degrees of the edges in $\check{G}$. We employ the uncertain chromatic algorithm to find the uncertain chromatic set of uncertain graph $\check{G}$.

• Step 1 Initialize: for $\alpha =\alpha _{0}=0$, $\chi ^{\alpha }=5$.

• Step 2 The $\alpha$-cuts $G^{\alpha }=(V,E^{\alpha })$ for $0<\alpha _{i}<\alpha \le \alpha _{i+1}$, $i=1,2,\ldots ,8$ are given in Table 3.

• Step 3 The $\alpha$-cut chromatic numbers are given in Table 3.

• Step 4 Put $T_{4}=\{\alpha |0<\alpha \le 0.1,\chi ^{\alpha }=4\}$, $T_{3}=\{\alpha |0.1<\alpha \le 0.5,\chi ^{\alpha }=3\}$, $T_{2}=\{\alpha |0.5<\alpha \le 1,\chi ^{\alpha }=2\}$, and $T_{1}=\emptyset$. $\beta _{1}=0$, $\mathcal {M}\{\pi _{1}=1\}=\beta _{1}=0$, $\beta _{2}=1- \inf \{\alpha |\alpha \in T_{2}\}=1-0.5=0.5$, $\mathcal {M}\{\pi _{2}=1\}=\beta _{2}=0.5$, $\beta _{3}=1- \inf \{\alpha |\alpha \in T_{3}\}=1-0.1=0.9$, $\mathcal {M}\{\pi _{3}=1\}=\beta _{3}=0.9$, $\beta _{4}=1- \inf \{\alpha |\alpha \in T_{4}\}=1-0=1$, $\mathcal {M}\{\pi _{4}=1\}=\beta _{4}=1$, $\beta _{5}=1$, and $\mathcal {M}\{\pi _{5}=1\}=\beta _{5}=1$.

• Step 5 The uncertain chromatic set is $\rho (\check{G})=\{(\pi _{1},0),(\pi _{2},0.5),(\pi _{3},0.9),(\pi _{4},1),(\pi _{5},1)\}$.

Table 3 List of $\alpha$-cut with different cut levels, the family of independent vertex sets in $G^{\alpha }$ and $\chi ^{\alpha }$

5 Application

In this section, we give an application of the uncertain chromatic set of an uncertain graph for the problem of minimizing the number of storage containers for all of the chemicals in a laboratory.

Assume that some chemicals exist in a laboratory. Two chemicals with different characteristics can make for some dangerous situations, such as producing poisonous gas, explosions, etc. Chemicals with different characteristics are called incompatible. Otherwise, the chemicals with the same characteristics are called compatible.

If two incompatible chemicals are placed in the same container, then the condition will not be secure. The problem is to determine the minimum number of containers needed in the laboratory such that security is maximized. If the situation is modeled by a crisp graph, then there are only two choices for a given set of two vertices: either the two vertices are incompatible or the two vertices are compatible. However, because of the lack of observation data, the incompatibility between two vertices may not be completely determined. Therefore, the situation cannot be handled by a crisp graph.

Assume that we lack of observation data for whether two chemicals are incompatible or not. Hence, we deal with the situation on uncertainty theory and we model the situation by an uncertain graph $\check{G}=(V,E,\xi )$ which is based on uncertainty theory. The vertices of uncertain graph $\check{G}$ represent the chemicals and two vertices are adjacent if their corresponding chemicals are incompatible. Otherwise, two vertices are not adjacent if their corresponding chemicals are compatible. The lower the value $\alpha$ is, the greater the $\alpha$-cut chromatic number is. In other words, the lower the value of $\alpha$, the greater the incompatibility of the chemicals. This means the condition requires a higher level of security, i.e., a greater number of storage containers is needed. Otherwise, the bigger the value $\alpha$ is, the lower the $\alpha$-cut chromatic number is. In other words, the greater the value of $\alpha$, the greater the compatibility of the chemicals. Here the condition demands a lower level of security, and we require fewer storage containers.

Let $\Lambda _{k}$ be an uncertain event corresponds to the proposition that “the minimum number of containers needed is approximately k”. The Boolean uncertain variable $\pi _{k}=1$ indicates that the event $\Lambda _{k}$ may occur and $\pi _{k}=0$ indicates that the event $\Lambda _{k}$ is impossible. The problem of determining the minimum number of containers needed in the laboratory can be solved by finding the uncertain chromatic set $\rho (\check{G})=\{(\pi _{k},\mathcal {M}\{\pi _{k}=1\})\}$, where the uncertain measure $\mathcal {M}\{\pi _{k}=1\}=\beta _{k}$ and $\mathcal {M}\{\pi _{k}=0\}=1-\beta _{k}$ for $k=1,2,\ldots ,n$. The uncertain measure $\mathcal {M}\{\pi _{k}=1\}$ indicates the belief degree of the secure condition if we use the k containers in the laboratory. Now, we give an example to illustrate an application of uncertain graph coloring.

Example 5.1

Consider the uncertain graph $\check{G}=(V,E,\xi )$ given in Fig. 1. There are five vertices associated with five chemicals in the laboratory. All of the edges in uncertain graph $\check{G}$ are associated with some pairs of chemicals, which are incompatible with the belief degrees $A=\{0.1, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 1\}$. The problem of minimizing the number of containers for the chemicals will be solved by finding the uncertain chromatic set of uncertain graph $\check{G}$.

It follows from the previous example that the uncertain chromatic set is

$$\begin{aligned} \rho (\check{G})=\{(\pi _{1},0),(\pi _{2},0.5),(\pi _{3},0.9),(\pi _{4},1),(\pi _{5},1)\}. \end{aligned}$$

The result can be interpreted as follows.

• 1. If the minimum number of container is 1, then the belief degree of the secure condition is 0, meaning the condition is not safe.

• 2. If the minimum number of container is 2, then the belief degree of the secure condition is 0.5. We can put the chemicals $\{A,C,D\}$ in one container and the chemicals $\{B,E\}$ in another one.

• 3. If the minimum number of container is 3, then the belief degree of the secure condition is 0.9. We can put the chemicals $\{A,C,E\}$ in the first container, $\{B\}$ in the second and $\{D\}$ in the third. There are other scenarios involving 3 containers shown in Table 3.

• 4. If the minimum number of container is 4 or 5, then the belief degree of the secure condition is 1, meaning the condition is very safe. We can put each incompatible chemical into different containers.

6 Innovations and comparisons

This section presents the innovations and advantages of the proposed work. After that, we compare the proposed work with the existing works (Muñoz et al. 2005; Chen and Peng 2014).

6.1 Innovations of the proposed work

The innovations and advantages of this research are presented as follows.

• 1. In the crisp graph, the adjacency between two vertices is deterministic. However, in a real-life situation, some indeterminate factors will appear because of the lack of observation data, insufficient information and other reasons. In such cases, the adjacency between two vertices is not completely determined. Hence, we cannot handle such a situation by a crisp graph. However, by taking advantage of uncertainty theory, some indeterminate factors in the adjacency of vertices can be handled by uncertain variables.

• 2. One of the coloring problems of a crisp graph G is to determine the chromatic number of G, which is a crisp number. In practical applications, as discussed in the previous sections, the crisp chromatic number cannot handle some of the indeterminate factors in a coloring problem. However, through uncertain graph coloring, we obtain an uncertain chromatic set which is a useful tool to handle uncertain factors in the coloring problem.

We summarize the innovations and advantages of the proposed work in Table 4.

Table 4 Innovations and advantages of the proposed work

6.2 Comparisons with the existing work

We compare the proposed work to the existing work as given in the relevant literatures (Chen and Peng 2014; Muñoz et al. 2005). Muñoz et al. (2005) discuss the coloring problem of fuzzy graphs. The former focuses on constructing a fuzzy chromatic set of a fuzzy graph based on the concept of a maximal fuzzy independent vertex set. The later discusses the coloring method for fuzzy graphs based on an $\alpha$-cut of a fuzzy graph. By employing the concept of the $\alpha$-cut of a fuzzy set, Muñoz et al. (2005) constructed the concept of an $\alpha$-cut of a fuzzy graph. Furthermore, they introduced a fuzzy chromatic number of a fuzzy graph based on the concept of fuzzy number.

However in a real-life problem, there are times when we have incomplete information which cannot be dealt with fuzzy theory via possibility measure. We provide an illustration to explain this problem. Assume that the vertices in a graph represent people and the edges join pairs of friends in the graph. Whether two people are friends is not exactly known. Observed information of the friendship for any two people does not necessary exist. Based on the concept of possibility measure in fuzzy theory, we can obtain the following results:

$$\begin{aligned} \text{ Possibility } \{\text{ the } \text{ people, } \text{ who } \text{ are } \text{ friends, } \text{ are } \text{ exactly } \text{25 }\}= & {} 1,\\ \text{ Possibility } \{\text{ the } \text{ people, } \text{ who } \text{ are } \text{ not } \text{ friends, } \text{ are } \text{ exactly } \text{25 }\}= & {} 1, \text {etc}. \end{aligned}$$

Table 5 Comparison between the proposed work and the existing work

These results are not reasonable within theoretical mathematics. In order to handle this difficulty, Liu (2007) introduced an uncertain measure, a self-dual measure, within the framework of uncertainty theory. Therefore, we work on an uncertain graph which is based on uncertainty theory. An uncertain graph is a useful tool for modeling uncertain phenomenon in real-life situations. Our work focuses on a coloring method for uncertain graph by means of coloring the $\alpha$-cut of uncertain graph. To the best of our knowledge, no one has introduced the concept of an $\alpha$-cut of an uncertain graph before. The similarities between the paper of Muñoz et al. (2005) and this paper are that both discuss the concept of an $\alpha$-cut of a non deterministic graph, and that the principal goal is to transform coloring of a nondeterministic graph into classical coloring by means of an $\alpha$-cut. Hence, the steps given in Muñoz et al. (2005) and in this paper are simple and easy. The differences between our proposed work and the existing work in Muñoz et al. (2005) are discussed as follows.

• 1. Muñoz et al. (2005) worked on a fuzzy graph which is based on fuzzy set theory. The indeterminate factors on the edges were handled by a fuzzy edge set. They defined the concept of an $\alpha$-cut of a fuzzy graph by employing the concept of an $\alpha$-cut of a fuzzy set. Further, they defined a fuzzy chromatic number by means of the concept of fuzzy number. However, the concept of a fuzzy chromatic number defined by Muñoz et al. (2005) is not consistent with the chromatic number of a crisp graph.

• 2. We focus on an uncertain graph which is based on uncertainty theory. The indeterminate factors on the edges are handled by uncertain variables. In this paper, the concept of an $\alpha$-cut of an uncertain graph is introduced. Then, coloring of the uncertain graph $\check{G}$ is transformed into the classical coloring via the $\alpha$-cut of $\check{G}$. Every $\alpha$-cut chromatic number may be a chromatic number of the uncertain graph $\check{G}$. Hence, we have an uncertain event $\Lambda _{k}$ corresponds to the proposition that “the chromatic numbers of $\check{G}$ is approximately k”, and define the belief degree of each event. We represent the existence of each event by a Boolean uncertain variable $\pi _{k}$. That is, if the event $\Lambda _{k}$ exists for the uncertain graph $\check{G}$, then $\pi _{k}=1$. Otherwise, $\pi _{k}=0$. Further, an uncertain chromatic set of uncertain graph $\check{G}$ is defined as a set $\rho (\check{G})=\{(\pi _{k},\mathcal {M}\{\pi _{k}=1\})\}$. The chromatic number for the underlying graph $G^{*}$ of the uncertain graph $\check{G}$ corresponds to $\pi _{k}$ with the belief degree $\mathcal {M}\{\pi _{k}=1\}=1$. Therefore, the concept of an uncertain chromatic set is consistent with the chromatic number of a crisp graph.

The similarity between the existing work (Chen and Peng 2014) and this work is obvious: both study the coloring problem within the framework of uncertainty theory. The differences between this work and the existing work (Chen and Peng 2014) are discussed as follows. We summarize the comparison between the proposed work and the existing work in Table 5.

• 1. Chen and Peng (2014) introduced the concepts of an uncertain independent vertex set and a maximal uncertain independent vertex set of an uncertain graph. Then, they focused on the method to determine the uncertain chromatic set of an uncertain graph based on maximal uncertain independent vertex set. This means they did not transform coloring of an uncertain graph into the classical coloring. Hence, the steps based on maximal uncertain independent vertex set (Chen and Peng 2014) are highly complex and time consuming.

• 2. In this paper, we color the uncertain graph $\check{G}$ by transforming it into the classical coloring via the $\alpha$-cut of $\check{G}$. Next, we determine the uncertain chromatic number for uncertain graph $\check{G}$ via an $\alpha$-cut chromatic number. Therefore, the steps used in this proposed algorithm are simpler and easier than that of based on a maximal uncertain independent vertex set (Chen and Peng 2014).

7 Conclusions

In this paper, we proposed the concept of the $\alpha$-cut of an uncertain graph in order to deal with uncertain graphs by means of crisp graphs. Next, some properties of the $\alpha$-cut of an uncertain graph were investigated. One of the effective methods for solving the coloring problem in the nondeterministic graph is to transform it into classical coloring. Hence, we colored an uncertain graph via $\alpha$-cut coloring and obtained $\alpha$-cut chromatic number, we also discussed some properties of the $\alpha$-cut chromatic number.

Furthermore, we proposed an uncertain chromatic algorithm based on $\alpha$-cut coloring. The algorithm was decomposed into two steps. The first step was to find the $\alpha$-cut chromatic number of an uncertain graph. The second step was to find the uncertain chromatic set of an uncertain graph. Any algorithm for computing the chromatic number of a crisp graph could be used to compute the $\alpha$-cut chromatic number. Therefore, the uncertain chromatic algorithm proposed in this paper was simpler and easier than the algorithm based on a maximal uncertain independent vertex set. Finally, a real-life decision making problem was given to show the application of the uncertain chromatic set and to show the feasibility and efficiency of the uncertain chromatic algorithm.

There are several promising future directions for extending our paper. First, a complexity analysis of the proposed method is an interesting problem for completing our manuscript. Therefore, we can continue this research by investigating the complexity analysis of the proposed method and compare it with the complexity analysis of the method given by Chen and Peng (2014). Second, we can use uncertain programming to deal with the vertex coloring problem of an uncertain graph. Finally, we can employ the current results to solve more real-life decision making problems.