一种构造k—色临界图的方法  

One Means of Constructing K-Chromatically Critical Graphs

作　　者：李雪峰[1] 

机构地区：[1]西安邮电学院,陕西西安710121

出　　处：《廊坊师范学院学报（自然科学版）》2009年第3期7-8,共2页Journal of Langfang Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60672026);陕西省自然科学基金资助项目(2006A12)

摘　　要：图G的色数χ(G)是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有χ(H)<χ(G)=k,则称G是k—色临界的,因此可以给出一种构造k—色临界图的方法。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.

关 键 词：可k-着色 色数 临界图 

分 类 号：O157.5[理学—数学]