【摘要】 图G的色数χ(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有χ(H)<χ(G)=k,则称G是k—色临界的,因此可以给出一种构造k—色临界图的方法。更多还原

【Abstract】 The chromatic number χ(G) of graph G is the least color number k if its vertices can be colored with k colors so that no two adjacent vertices have the same color.G is said to be k-critical graph if χ(H)<χ(G)=k for every proper subgraph H of G.In this paper,one means of constructing k-chromatically critical graphs is gived.更多还原