论文部分内容阅读
对两个正整数1≤d≤k,图G的k/d圆着色是映射c∶V(G)(→){0,1,...,k-1}满足:当uv∈E(G)时,d≤|c(u)-c(v)|≤k-d.图G的圆色数,记作χc(G),是最小的有理数k/d使得图G存在一个k/d圆着色.图G的圆团数,记作ωc(G),是最大的有理数k/d满足存在一个从Kk/d到G的同态。图G称为圆完美的,若对G的任意导出真子图H满足ωc(H)=χc(H).如果一个图本身不是圆完美的,但它的任意导出真子图是圆完美的,那么我们称这个图是极小非圆完美的。极小非圆完美图结构的研究是研究圆完美图的结构的极其重要的途径,而且越来越多的证据显示,极小非圆完美图的结构非常复杂.在这篇文章中,我们发现:满足一定条件的花是极小非圆完美的。并且我们从Kk/d出发,构造了多种类型的极小非圆完美图,其中一种构造方案是删去Kk/d的一条边,但这样的操作得满足一定的条件才可行,文中给出了相应的结果。最后,我们猜测G=Kk/de(其中e∈Kk/d)不是极小非圆完美图只有两种情况:要么ωc(G)=χc(G),要么H含有导出真子图H是非圆完美的,并且H是我们已经发现的通过删去Kk/d的一条边得到的一些极小非圆完美图.