图论与组合数学是数学的一个分支，它的历史可以追溯到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）.