摘要
在一个给定图中,研究消色数的大小自然是一个问题,但对于一般图而言,确定它们的消色数是非常困难的,这已被Yanakakis and Garri证明。文章刻画了完全κ-部图中消色的数为1,2和3的图并且确定了路图的消色数和极大外可平面图消色数的下界。
To study how large the achromatic number in given graph is a number in given graph is a natural question,but for general graphs,it is hard problem to determine their achromatic number,which proved by Yanakakis and Garri.In this paper,we characterize graphs having a given achromatic number κ with achromatic number 1,2 and 3.We also determine the achromatic number of par
出处
《新疆师范大学学报(自然科学版)》
2011年第1期95-100,共6页
Journal of Xinjiang Normal University(Natural Sciences Edition)
关键词
完全κ-着色
消色数
同态
Complete-coloring
Achromatic number
Homomorphism