Vertex Coloring for Uncertain Graph

摘要：

　　A graph is called an uncertain graph if the edges in the graph are not determined,and exist with some belief degrees described by uncertain measure.This paper investigates the vertex coloring problem in an uncertain graph.At first,we originally propose the concept of uncertain independent vertex set and maximal uncertain independent vertex set.Based on the maximal uncertain independent vertex set,we propose the concept of uncertain chromatic set.Then,an algorithm is derived to obtain the uncertain chromatic set,and we can find how to color the vertex of an uncertain graph by means of uncertain chromatic set.Finally,a numerical example is presented to show the effectiveness of the proposed algorithm.

关键词： Vertex coloring problem Maximal uncertain independent vertex set Uncertain chromatic set Uncertainty theory Uncertain graph

作者: Lin Chen Jin Peng

作者单位: College of Mathematics and Sciences,Shanghai Normal University,Shanghai 200234,China;Institute of Un Institute of Uncertain Systems,Huanggang Normal University,Hubei 438000,China

会议类型: 国内会议

会议名称: 第十二届中国不确定系统年会暨第十六届中国青年信息与管理学者大会

会议地点: 香港

会议语种:英文

页码: 191-199

在线出版日期: 2014-07-27（万方平台首次上网日期，不代表论文的发表时间）