论文部分内容阅读
超图是普通图的推广,普通图的着色在图论中占有重要地位。现已形成着色理论。而超图的着色作为普通图的着色的推广,其研究意义自然更加深刻,内容更加丰富,适用范围自然更为广泛。这篇文章主要研究了超图的着色并获得了一些相关结果。
第一部分介绍了与本文有关的基本概念及其为什么要研究图和超图的着色问题。从而说明研究超图的着色是有重要意义的。
第二部分研究了超图的多项式与着色的关系,用超图的多项式刻画了超图的着色。特别对超图的2-色多项式进行了具体研究。并且得到了判断一个超图不能2-着色的充要条件及可以2-着色的充分条件。接着又对边数等于顶点数的超图进行了研究,得到了可以2-着色的充分条件。最后由本文定义的多项式得到了一般超图色数的一个上界。
第三部分研究了超图的着色与Lovász引理的关系,我们利用Lovász局部引理给出超图可以t-着色的一个充分条件以及对其进行t-着色使得每种颜色在每条边中均出现的充分条件。接着给出了对超图进行2-着色使得每种颜色在每条边中至少出现两次的充分条件。并将该定理推广到t-着色。
第四部分研究了一些构图方式,对一些复合超图得到了其色数,另外的一些得到了它们的界。
第五部分研究了超图的强着色的一些性质。并确定了某些特殊超图的强色数。与此同时,也提出了关于超图强着色可以进一步研究的一些问题。