平面图的放松均匀染色与强边染色

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:px520
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G=(V,E),图G的一个正常的k-点(边)染色就是k种颜色对点(边)的分配,使得任意相邻的点(边)分配到不同的颜色.一个正常的点染色如果每个色类的大小至多差1,称染色是均匀的.图G的均匀染色数是使得图G是均匀m-可染的最小的整数m,用χeq(G)表示.一个放松的k-染色是对点的k-染色使得每个点与至多一个邻点染相同的颜色.图G的一个放松均匀k-染色(简记ED-k-染色)是图G的点集的一个放松的k-染色使得任意两个色类的大小至多差1.图G的ED-色数是使得G是ED-m-可染的最小整数m,记为χed(G).图G的ED-染色阈值是使得图G对任意n≥ m都是ED-n-可染的最小整数m,记为χed*(G).本文我们证明最小度至少2且围长至少为8的平面图有χed*(G)≤4.图的强边染色是一种正常边染色.要求任何长至多为3的路上的边都染不同的颜色.使得图有一个强边染色的最小颜色数称为图的强边色数.用χ’s(G)表示.Faudree等人证明任意最大度为△的平面图有χ’s(G)≤ 4△+4.那么△=4时.χ’s(G)≤ 20.最近,Wang等人证得其强边色数不超过19.本文中我们证明不含带弦5-圈和梯子图L3的平面图是18-强边可染的.并且,对最大度为4的平面图,若它是一个非18-强可染的边数极小图.则它一定不存在至多含三条边的非平凡边割.本论文共分为四章.主要研究了平面图的放松均匀染色问题和强边染色问题.第一章,我们主要介绍了图染色问题的背景及意义,给出了本中用到的基本概念与符号,阐述了放松均匀染色和强边染色问题的研究现状,及本文的主要结果.第二章,我们研究了围长至少为8的平面图的放松均匀染色,证明其对任意m≥4都是ED-m-可染的.第三章,我们研究了最大度为4的平面图18-强边染色,给出了一个充分条件.此外,基于图的k-边割,我们讨论了非18-强边可染的极小图的结构.第四章,我们给出了可进一步研究的问题.
其他文献
一九八二年十二月四日,朱受群同志就郭沫若担任北伐军总政治部副主任的时间问题,写信请教杭州大学孙席珍教授。孙教授于一九八三年一月二十七日给朱受群同志复了信,并附言:“
为了更好地研究土壤含水率的变化情况,设计制作了一套由ATmega128单片机、μC/OS-Ⅱ操作系统、BD-Ⅰ型土壤水分传感器、RS-485以及RS-232总线式数据传输等组成的土壤水分监测
据中国机械工业联合会、机械工业景气监测中心的统计表明,受全国性城乡电网改造的影响,电工电器行业已成为机械工业中增长较快的一个行业,今年头两个月全国电工电器行业共实
前不久,中央电视台CCTV2《中国财经报道》节目主持人,风度翩翩的赵赫,(他无论什么时候,都是一副胸有成竹的姿态),在对“中石化”上市一片叫好声中,他众人皆醉我独醒地说,流通盘高达218
我国的交响音乐发展始于30年代,老一辈的作曲家如洗星海、黄自、萧友梅等写有一批具拓荒性质的作品(大约有18部作品)。由于当时旧中国政治动乱、经济落后,所以这些作品的社会
为了解二氧化硅(SiO2)对涂料的影响,将粉状SiO2加入聚氨酯涂料中,并涂饰于马尾松木材表面,以达到改良木材表面性质的目的.结果表明:利用硅烷偶联剂KH-570在甲苯溶剂中改性的SiO2的疏水亲油性增强,其在聚氨酯涂料中的分散性优于未改性SiO2;SiO2在一定程度上提高了木材表面漆膜的性能,漆膜的耐冲击性、抗老化性能得到显著提高;加入改性SiO2的聚氨酯涂料性能在耐磨性、硬度、耐冲击性、耐老化
近来,失智老人及其认知能力干预逐渐引起了社会关注。失智是指由于慢性或进行性大脑结构的器质性损害引起的高级大脑功能障碍的一组症候群,是患者在意识清醒状态下出现的,持
复合材料广泛应用于船舶上层建筑及其内部结构,势必会带来复合材料与钢质甲板间的连接可靠性问题。连接结构是船体结构的薄弱环节,其性能特征关系到整船的安全,因此,本文以船用复合材料与金属连接问题为研究背景,通过设计新型复合材料与金属混杂连接接头,研究连接接头在静力和疲劳载荷下的强度特性、失效模式、疲劳寿命等力学性能,为船舶复合材料连接结构的设计及实际应用等提供有益的参考。首先,进行了混杂连接接头的构型设
随着先进制造技术的不断发展和中职院校课程改革的不断深入,3D打印技术的应用前景引起了中职院校教育工作者的广泛关注。笔者所在学校将3D打印技术打造成数控加工专业(中级技能)一门新增先进制造技术实训课程。课程设立的初衷是让数控加工专业的学生多接触先进制造技术,培养学生创新能力和实践能力,激发学生的学习兴趣,促进其职业素养与职业责任感的建立与提升。中职教育是职业教育的重要组成部分,中等职业教育发展水平的