论文部分内容阅读
研究和讨论了图的顶点着色问题中k色图的连通性，利用归纳与迭代的方法证明了对于任何k色连通图G，存在顶点y（G）的一个着色X1，X2，…，X4，使得对该着色类中任意顶点集Xi所诱导出的G^k的子图G^k（Xi）都是连通的。从而证明了Chen，Schelp和Shreve关于k色图的连通性的一个推测，最后将所得的结论作了进一步推广。