图的完全着色与消色数 (2011年)

在一个给定图中，研究消色数的大小自然是一个问题，但对于一般图而言，确定它们的消色数是非常困难的，这已被Yanakakis and Garri证明。文章刻画了完全k-部图中消色的数为1，2和3的图并且确定了路图的消色数和极大外可平面图消色数的下界。