论文部分内容阅读
图论与组合数学是数学的一个分支,它的历史可以追溯到18世纪,最早来源于Euler关于哥尼斯堡七桥问题的研究,并且至今仍然具有很强的活力.它在计算机科学,生命科学以及其它科学中具有很多的应用. 我们首先研究的是图的染色问题,这里提到的图都是简单,无向,有限图. 图G的全染色是指对图的点和边同时进行染色,使得相邻的点,相邻的边以及相关联的点和边都染不同颜色.对于G的一个全染色φ,我们用Cφ(v)来表示点v的颜色以及v周围边的颜色的集合.我们称点v和点u是冲突的,如果两点相邻且Cφ(v)=Cφ(u).如果G中任意两个相邻点都不冲突,我们就称这种全染色是邻点可区别的.我们将能保证G具有邻点可区别全染色的最小的颜色数k称为图G的邻点可区别全色数,记做x"a(G).张忠辅等人首先提出这种染色并猜想:对于至少有两个点的图G,其邻点可区别全色数满足x"a(G)≤△(G)+3.黄丹君等人已经证明了对于最大度△(G)≥11的平面图,上述猜想成立.本文在第2章中证明了对于最大度△(G)≥10的可嵌入到欧拉示性数非负曲面上的图,以及△(G)≥8,且5-圈至多含一条弦的可嵌入到欧拉示性数非负曲面上的图,上述猜想成立,推广了原来的结论. 对于给定图G=(V, E),给每一个x∈V∪E分配一个颜色集合Lx.如果G存在一个邻点可区别全染色φ使得对于所有的x∈V∪E都有φ(x)∈Lx,我们就称G是邻点可区别全-L-可染的,如果对于每一个x∈V∪E,均有|Lx|≥k,我们称G是邻点可区别全-k-列表可染的,使得G是邻点可区别全-k-列表可染的的最小的整数k称为图G的邻点可区别列表全色数,用符号ch"a(G)来表示.本文在第3章中证明了若G是最大度满足△(G)≥10的平面图,或者最大度满足△(G)≥11的可嵌入到欧拉示性数非负曲面上的图,则ch"a(G)≤△(G)+3. 假设φ是图G的一个全染色,v是G中的一个点,我们用Cφ(v)来表示点v的颜色以及与v关联的边的颜色,用mφ(v)来表示Cφ(v)中颜色的和.对于相邻的两个点u和v,如果mφ(u)=mφ(v),我们就称这两点是相互冲突的,如果任意两个相邻的点都不冲突,这个染色就称为G的邻和可区别全染色,能保证G具有邻和可区别全染色的最小的颜色数k就称为G的邻和可区别全色数,记为x"nsd(G).Pil(s)niak和Wo(z)niak猜想对于至少有两个点的图G,其邻和可区别全色数满足x"nad(G)≤△(G)+3.本文在第4章中证明了若G是最大度满足△(G)≥14的平面图,则x"nsd(G)≤△(G)+2. 在第5章中,我们主要考虑了一类特殊超图的Turán数问题.对于一个图G,将G的每一条边增加r-2个新点扩张成一个r-集合,且不同的边增加的点不同,这样就得到一个r-一致超图,我们称这个r-一致超图为G的r-扩张,用G(r)表示.超图H的Turán数exr(n,H)是指点数为n的不含H做为子图的r-一致超图所能含有的最大边数.早在1964年Erd(o)s已经证明了当且仅当x(G)>r时exr(n,G(r))与nr同阶,然而当x(G)≤r时,exr(n,G(r))并没有得到充分的研究,即使是r=2时的情况.我们的结论是:如果r是满足r≥5的整数,G是树宽至多为2的图,那么对于足够大的n,exr(n,G(r))~(σ(G)-1+o(1))(n r-1).