超图的顶点着色

论文摘要

超图是普通图的推广,普通图的着色在图论中占有重要地位。现已形成着色理论。而超图的着色作为普通图的着色的推广,其研究意义自然更加深刻,内容更加丰富,适用范围自然更为广泛。这篇文章主要研究了超图的着色并获得了一些相关结果。第一部分介绍了与本文有关的基本概念及其为什么要研究图和超图的着色问题。从而说明研究超图的着色是有重要意义的。第二部分研究了超图的多项式与着色的关系,用超图的多项式刻画了超图的着色。特别对超图的2-色多项式进行了具体研究。并且得到了判断一个超图不能2-着色的充要条件及可以2-着色的充分条件。接着又对边数等于顶点数的超图进行了研究,得到了可以2-着色的充分条件。最后由本人定义的多项式得到了一般超图色数的一个上界。这一部分的主要结果如下:命题2.2.H不能2-着色当且仅当p（H）=0,对所有的xi∈{0,1}。命题2.3.如果q（H）的某个系数满足q（H）（?）0（modki）（i 1,2,…,t）,那么H可以2-可着色。定理2.1.如果perm（M）（?）0（modki）（i=1,2,…,t）,那么H可以2-着色。定理2.2.如果对任意的i,若（?）|Ej{i}|pcrm Mji（?）0（mod 2 ki）那么H可以2-可着色。定理2.3.设H是一个简单超图,那么有x（H）≤s+1。第三部分研究了超图的着色与Lov（?）sz引理的关系,我们利用Lov（?）sz局部引理给出超图可以t-着色的一个充分条件以及对其进行t-着色使得每种颜色在每条边中均出现的充分条件。接着给出了对超图进行2-着色使得每种颜色在每条边中至少出现两次的充分条件。并将该定理推广到t-着色。这一部分的主要结果如下:定理3.3.设H是一个超图,且H的每条边至少有k个点且至多与d条其它的边相交。令t≥2是一个整数。如果e（（d+1）（t-1）+1）t（-k）≤1,那么H有一个t-着色。定理3.4.设H是一个超图,且H的每条边至少有k个点且至多与d条其它的边相交。令t≥2是一个整数。如果e（（d+1）（t-1）+1）（1-（?））k≤1,那么H有一个t-着色且每种颜色在每条边种均出现。定理3.5.设H是一个超图,每条边包含至少k（k≥4）个点,且至多于d条其它的边相交。如果有e（k+1）2-k（d+2）≤1,那么H有一个2-着色且每种颜色在每条边至少出现两次。推广定理.设H是一个超图满足其每条包含至少k（k≥2t）个点且至多于d条其它的边相交。令t≥2,如果e（1-（?））k-1（1-（?）+（?））（d+2）≤1,那么H有一个t-着色使每种颜色在每条边中至少出现两次。第四部分研究了一些构图方式,对一些复合超图得到了其色数,另外的一些得到了它们的界。这一部分的主要结果如下:命题4.1.设H1和H2是两个超图,且x（H1）=λ1,x（H2）=λ2,那么x（H1+H2）=max{λ1,λ2)。命题4.2.设H1和H2是两个超图,其中x（H1）λ1,x（H2）λ2。那么,x（H1（?）H2）-2。命题4.3.设H1和H2是两个超图且x（H1）λ1,x（H2）λ2。那么,x（H1∪H2）≤λ1·λ2。命题4.4.设H1和H2是两个超图,满足x（H1）=λ1,x（H2）=λ2。那么x（H1·H2）≤min{λ1,λ2}.命题4.5.设H1和H2是两个超图,满足x（H1）=λ1,x（H2）=λ2。那么x（H1×H2）≤min{λ1,λ2}。第五部分研究了超图的强着色的一些性质。并确定了某些特殊超图的强色数（详见例1-例5）。与此同时,也提出了关于超图强着色可以进一步研究的一些问题。

论文目录

• 中文摘要
• Abstract
• 文献综述
• 1.引言
• 1.1 超图的基本概念
• 1.2 研究背景
• 2.多项式在超图着色上的应用
• 2.1 基本概念及研究背景
• 2.2 主要结果
• 3.Lov（?）sz局部引理在超图着色的应用
• 3.1 研究背景及已知结果
• 3.2 主要结果
• 4.复合超图的色数
• 4.1 研究背景
• 4.2 主要结果
• 5.超图的强着色
• 5.1 强着色的基本概念
• 5.2 常见的超图的强着色数
• 5.3 进一步研究的背景及问题
• 参考文献
• 致谢