图的完全着色与消色数

Complete Coloring and the Achromatic Number of Graphs

在一个给定图中,研究消色数的大小自然是一个问题,但对于一般图而言,确定它们的消色数是非常困难的,这已被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