二部图的列表着色问题

来源 :新疆大学 | 被引量 : 0次 | 上传用户:lkj0062
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
列表着色的概念既是图着色概念的一个推广,又与图着色的概念有许多不同之处。列表着色主要研究的问题是确定图的列表色数 然而,这项工作似乎是比较困难的,即使是对二部图,也没有成熟的结果。因此,本文主要研究的是二部图的可选性。 N. Alon在『8]中通过,弋教的方法证明了,每个二部图G是(『/I(G)]+1)一可选的。从而,可得每个二部图G是可选的。在『7]中,黄琼湘和王国平同样利用代教方法,证明了每个二部图G是一可选的,这里这改进了[8]中所得到的结果,并且从该结果,我们同样也可以得到二部图G是可选的。基于以上工怍,在本文中,我们首先考虑的是完全二部图。通过“色度”这个概念的引进并利用图论的方法,我们证明了完全二部图是出可选的,从而进一步证明了二部图G是可选的,如果△(G)≥6。所得结果是对『8]中关于二部图可选性的已有结果的另一个改进。 1979年,Erdos,Rubin和Taylor在『2]中对所有2一可选的图进行了分类。但对3一可选图的分类还未完成,即使对3一可选的二部图,也仅是在『4]和『5]中有一些相关结果。事实上,这是一项困难的工怍即使是对3一可选的完全二部图,也是如此。因此,我们考虑条件较弱一类图的分类问题,即对所有(2,3)一可选的完全二部图进行分类。我们给出了所有的(2,3)一可选的完全二部图,星图、(m+n≤9且当n一4时m≠5),相信此结果对研究3一可选二部图会有一定帮助。
其他文献
作为曾经为英语发愁的"小可怜",我尝试征服这座"大山"的方法可谓花样百出。小结自己多年英语学习的目标,我想用一个词来形容,即"实用"。这里,本着"减少痛苦"的人文关怀,为大家奉上一份实用主义者的英语学习心经。不妨先立目标面对英语庞大的词汇量和不胜枚举的特殊用法,任谁都会发出一声叹息:"吾生也有涯,而知也无涯。以有涯随无涯,殆已!"但我想告诉大家,我们行动之前必然有内在的驱动力,在决定好好学英
期刊
托福听力考试和大学英语六级听力考试具有相似性与相异性。该文从考试目的和考查的听力策略两个方面对比了两种考试的相异性并浅显地分析了托福听力考试对于大学英语六级听力考试的启发,旨在为改进大学英语六级听力考试提供一些思路。
以化工企业预处理后的废水为对象,以臭氧氧化技术为基础,加入铁刨花、载铁活性炭(Fe@AC)、铁碳球等含铁碳填料作为催化剂,考察不同臭氧投加量及废水初始pH条件下,对难降解化工废水出水COD的改善情况。结果表明,采用铁碳球为催化剂的臭氧-铁碳催化氧化工艺处理,降低难降解化工废水COD的效果明显优于单独臭氧氧化工艺;与以铁刨花、载铁活性炭(Fe@AC)作为填料的臭氧催化氧化相比,各反应阶段去除率均有不
随着城市的快速发展,城市道路日益拥挤,如何改善交通出行,发展好公共交通尤为重要。公交场站作为车辆停放的枢纽,其建设直接关系到整个交通业的发展,本文探讨将先进的物联网技术、通信技术、信息技术等高新技术应用于公交场站,以期通过标准化管理办法,实现城市公共交通行业数字化标准化转型升级,从而提高对场站的高效管理质量。
本文采用目前地表温度(Land Surface Temperature)反演方法中流行的单窗算法和劈窗算法,借助遥感技术,利用MODIS影像的第31通道和第32通道的亮度值反演出天山北坡地区2000年至2005年5年的7月份的地表温度,将研究区的地表温度划分出高温区(40℃—60℃。包括40℃,60℃)、中温区(30℃—40℃。不包括40℃,包括30℃)和低温区(0℃—30℃。不包括30℃,包括0
随着我国的移动互联网的快速化发展,促使直播行业不断发展。我国的直播行业发展主要涉及到了电商、游戏、社交等多个领域,因为涉及到的内容十分丰富所以受到了广大观众的喜爱,直播行业当前发展形势也会呈现出加速的状态,加强了对各个行业的赋能多元化因素探索。为了能够更好地对直播电商行业起到有效的规范发展,引导电商直播传递出更多的正能量内容,本文主要针对于现今金华直播电商行业的发展现状展开了调查工作,并针对存在的
本文讨论了求解无约束线性最小二乘问题的一种并行算法以及对它的改进。此算法是在n维空间中任取n+1个点,由这n+1个点构成一个单纯形,分别在各顶点与单纯形的重心的连线上进行一维搜索,从而得到新的n+1个点,可重新构成一个单纯形,重复以上步骤,直到单纯形的重心满足‖▽f(x)‖<ε为止,称这种算法为并行单纯形法。为了进一步加快算法的收敛速度,使并行单纯形法与共轭梯度法相结合,构成并行共轭梯度一单纯形法
子图覆盖问题是一个活跃且重要的研究课题,偶子图覆盖是子图覆盖的一个重要研究方向(习惯上,我们也称偶子图为圈)。在此领域已经产生了许多有趣且具有挑战性的问题,其中一些问题已被解决。例如,Bermond,Jackson和Jaeger[1]证明了每个无割边图有7个圈4覆盖。然而著名的圈双覆盖猜想仍旧没有被证实。Alspach和Zhang[2]证明了所有不含Petersen图的剖分子图的无割边图满足圈双覆
学位
学位