平面图的线性染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:Michellesy
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
用G=(V,E)表示一个有限简单无向图,顶点集为V,边集为E.如果G的一个映射φ:V→{1,2,...,k)满足当uv∈E,有φ(u)≠φ(v),则称φ是G的一个正常k-染色.若G有一个正常k-染色,则称G是k-可染的.图G的线性染色是G的一个正常染色使得染任意两种颜色的顶点集合导出子图是一些点不交的路的并.图G的所有线性染色中所用的最少颜色的个数称为G的线性色数,用lc(G)表示.   1973年,Grünbaum[1]提出了无圈染色的概念,图G的一个使得染任意两种颜色的顶点集合导出子图是一个森林的正常染色称为G的一个无圈染色.1998年,Yuster[2]提出了图的线性染色概念,并证明了任意图G都有lc(G)=O(△3/2),同时构造出了一类图满足lc(G)=Ω(△3/2).事实上,图的线性染色是无圈染色的一种特殊情形.   本学位论文改进和扩充了关于平面图线性染色的一些已有结果.设△和g(G)分别为图G的最大度和围长.本文的主要结果如下:   (1)对一个平面图G,若△≤6,则lc(G)≤2△+1;若△≥7,则lc(G)≤2△;   (2)若G是一个g(G)≥6的平面图,则lc(G)≤「△/2()+3;且当△(){4,5,...,12)时,有Ic(G)≤「△/2()+2;   (3)若G是一个g(G)≥5的平面图,则lc(G)≤「△/2()+5;且当△(){7,8,...,14)时,有lc(G)≤「△/2()+4;   (4)若G是g(G)≥4的平面图,则lc(G)≤「3△/2()+2.
其他文献
近年来,许多学者已在积分不等式理论方面作出了很多好的结果,例如B.G.Bondge,E.F.Beckenbach和B.G.Pachpatte等.特别是B.G.Pachpatte在关于两个独立变量的积分不等式方面得到
学位
随着科学技术的不断发展,数学中各种各样的问题越来越引起人们的广泛关注,比如作为数学中重要分支的椭圆方程和基尔霍夫问题,因其能很好的解决实际生产中的各种问题而受到了
学位
采用Muskhelishvili方法,通过构造保角变换把复杂缺陷映射到单位圆内部或外部,将平面弹性问题转化为求解满足一定边界条件的两个复势函数φ(z),Ψ(z).利用Cauchy积分、定积分理
近代物理学和应用数学的发展,要求分析和控制客观现象的数学能力向着富有全局性的高、精水平发展,从而使非线性分析成果不断积累,逐步形成了现代分析数学的一个重要的分支学
学位