平面图的线性染色

来源 :浙江师范大学 | 被引量 : 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在关于两个独立变量的积分不等式方面得到
学位
成人高等教育评估是保障成人高等教育质量的重要因素之一,是终身教育理念的时代要求,是学习型社会与和谐社会的核心要素.建立健全成人高等教育评估体系,开展现代意义上的成人
2018年3月28日,作为中集车辆(集团)有限公司(简称:中集车辆集团)的全资下属企业,深圳中集专用车有限公司(简称:“深专”/“深圳专用车”)在其深圳市坪山工厂举行了一场大规模
期刊
古诗文是初中语文教材中重要一部分,在试卷中也占有重要分值,是初中学生要掌握的重点对象。中国五千年的悠久历史和灿n烂文化是一笔无比厚重的精神财富,也是中华民族取之不尽、
随着科学技术的不断发展,数学中各种各样的问题越来越引起人们的广泛关注,比如作为数学中重要分支的椭圆方程和基尔霍夫问题,因其能很好的解决实际生产中的各种问题而受到了
学位
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
采用Muskhelishvili方法,通过构造保角变换把复杂缺陷映射到单位圆内部或外部,将平面弹性问题转化为求解满足一定边界条件的两个复势函数φ(z),Ψ(z).利用Cauchy积分、定积分理
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
近代物理学和应用数学的发展,要求分析和控制客观现象的数学能力向着富有全局性的高、精水平发展,从而使非线性分析成果不断积累,逐步形成了现代分析数学的一个重要的分支学
学位