k+l色k-饱和图

k-SATURATED GRAPHS OF CHROMATIC NUMBER k+1

给出了一类具有较多边数的k+1色k-饱和图(不含K_k,但添加任一边都含K_k的图)的结构。导出了n点最大k+1色k-饱和图的边数的下界。

This paper considers the structure of k-saturated graphs ( K_kG but K_k∈G + e for all possible edges e)having chromatic number k+1 . A lower bound of |E(G)|is obtained, where |E(G)|denotes the number of edges of maximal k-saturated graph G having chromatic number k+1.