平面图邻接点区分边染色的一个结果

来源 :南京师范大学 | 被引量 : 0次 | 上传用户:buyaowenwo123456
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究了平面图的一类推广的边染色问题:邻接点区分边染色,所讨论的图均为简单图.  设φ:E(G)→{1,2,…,k}是从G的边集构成的集合E(G)到自然数集的一个映射,如果对任意相邻接的两个元素x,y∈E(G)均有φ(x)≠φ(y),则称φ是G的一个正常边染色.  邻接点区分染色是边染色的一中推广,这种染色对于图G的边可选用的颜色有一定的限制.我们用Cφ(v)来表示与顶点v相关联的边的颜色集合,即Cφ(v)={φ(uv)|uv∈E(G)}.如果φ是图G的一个正常边染色,同时对任意一对邻接点u和v满足Cφ(u)≠Cφ(v),则称φ是图G的一个邻接点区分边染色.我们用Xavd(G)来表示图G的邻接点区分边染色数,它是使得图G是邻接点区分边可染的最小的正整数k,即Xavd(G)=min{k|G是k-邻接点区分边可染的}.  Zhang等人[22]完全解决了路,圈,树,完全图和完全二部图的邻接点区分边染色问题,并提出一个重要猜想:如果图G是一个顶点数至少是3的连通图,且不是长为5的圈,那么图G的邻接点区分边染色数将不会超过△(G)+2.Balister, Hatami,卜月华,王维凡等人通过对图的最大平均度,可平面图的围长,最大度等的讨论,对这一猜想进行了一系列研究.其中卜月华,王维儿等人证明该猜想对围长至少为6的平面图是正确的.在本文中,我们将在卜月华,王维凡等人关于围长至少为6的平面图的一些结论的基础上,进一步把围长缩小至5,得到如下结论:  若图G是一个没有孤立边的平面图,且G的围长g(G)不小于5,则Xavd(G)≤△(G)+4.  这是一个几乎紧的界,因为Xavd(C5)=△(C5)+3.  本文第一章主要介绍一下基本概念和已有结论,第二章给出了围长大于等于5,没有孤立边的平面图的邻接点区分染色数,第三章给出了一些可以进一步研究的问题.
其他文献
去年暑假,我想买一辆自行车,妈妈毫不犹豫地答应了.正当我高兴得一蹦三尺高的时候,妈妈却提出了一个条件:到家里的蘑菇店打工21天,每天挣20元钱,攒够420元才能买自行车.看到
这天,我和妈妈愤愤不平地从老爸的车上下来,把老爸“太晚了”“太远了…别去了”的忠告抛到脑后,径直向大众公园走去.哼,不送就不送,我们自力更生!rn一路上,妈妈不停地问我:
现阶段,缺少实验设备和实验基地、教师的教学资源和教学经验匮乏,已经逐渐成为了制约中文专业实践教学发展的主要原因,为了能够有效解决这些问题,需要相关工作人员凭借自身经
一、课题提出的背景rn近年来,国内外对生命教育的研究越来越重视.我国目前高考指挥棒下高中教学功利性多些,人性价值少些,学生高考升学压力的不断增加,再加上高中生命教育的
期刊
网络一致性是复杂网络研究中的重要问题.本文讨论的是一类有领导者的多智能体系统的一般模型,并且假定自主体之间相互吸引的拓扑不同于自主体之间相互排斥的拓扑,除此之外每个
独家新闻是新闻中的珍品。几乎每一个记者,清晨走出家门的时候,都希望这天能抓到独家新闻。几乎每位读者,当他打开一张报纸,常常希望看到一篇乃至若干篇独家新闻。近几年来,
在我国教育事业不断受到重视的现代发展社会中,加快教育信息化建设已是教育界的共识,但如何进行有效的信息化建设却是各职业院校面临的共同问题.从整体来说,职业院校信息化建
对于戏曲,其作为我国中华民族传统文化中重要的艺术瑰宝,具有极高的教育价值,因而我国对其越发重视,特别是在教育上,开始大力推进戏曲进校园工作.基于此,本文就对当前戏曲进
在课改深入推进的今天,我所理解的校长的课程领导力就是从学校办学实际出发,按照党和国家的教育方针、政策,科学地组织课程规划、开发、实施、管理、评价的能力.学校的中心工
印度独立后,在移植西方民主政体的基础上,根据本国国情对其进行改造,建立了现代民主政体。印度独立以来,民主政体的蓝图不仅变成政治现实,而且经受住种种考验,一直成功地坚持下来。