摘要
唯一可着色图是指在不考虑颜色置换的情况下只有一个正常着色的图.判断一个图是否为唯一可着色的问题是NP-难的.文章从结构性质、存在性、构造等方面对唯一可着色图,特别是唯一3-可着色平面图的研究进行了介绍,并总结了一些目前尚未解决的问题.
A graph is uniquely colorable if it has only one proper coloring up to permutation of the colors.It has been proven that the problem of determining whether a graph is uniquely colorable is NP-hard.In this survey,we present the most important results on uniquely colorable graphs,especially on uniquely 3-colorable planar graphs,from the aspects of structural property,existence and construction and summarize some problems that have not been solved.
作者
李泽鹏
LI Ze-peng(School of Information Science and Engineering,Lanzhou University,Lanzhou 730000,China)
出处
《广州大学学报（自然科学版）》
CAS
2019年第4期60-68,共9页
Journal of Guangzhou University:Natural Science Edition
基金
国家自然科学基金资助项目(61802158)
关键词
唯一着色
图
平面图
构造
unique coloring
graph
planar graph
construction
