平面图的k-L(p,1)-可选性

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:wangxiaofu2008
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设N是正整数集,我们给图G的每个顶点v分配一个列表L(v),并且L(v)∈2N.如果图G有一个映射φ:φ(v)∈L(v),满足对于任意的v∈V(G),|L(v)|≥k,且使得对于任意两个顶点u和v,当d(u,v)=1时,|φ(u)-φ(v)| ≥p;当d(u,v)=2时,|φ(u)-φ(v)|≥1,这时我们就称图G是k-L(p,1)-可选的.使得图G是k-L(p,1)-可选的最小的k称为图G的k-L(p,1)-可选数,用χp,1l(G)表示.图G的一个染色φ:V(G)→{1,2,...,k},对于图G中的任意的两个顶点u和v,当d(u,v)≤2时,满足|φ(u)-φ(v)| ≥ 1,那么这个染色称为图G的二距离染色.使得图G有一个二距离染色的最小的k称为图G的二距离染色数,用X2(G)表示.对于k-L(p,1)-可选的图,当p=1时,图的k-L(1,1)-可选问题是比图的二距离染色问题更困难的一种染色.因为图的二距离染色要求每个顶点的可选颜色的列表都是{1,2,...,k},而k-L(1,1)-可选的每个顶点的可选颜色列表是任意的满足|L(v)| ≥ k 的,因此 X2(G)≤χ1,1l(G).在1977年,Wegner提出了有关平面图的二距离染色的一个非常重要的猜想:对于任意一个平面图G,(1)如果Δ(G)=3,那么χ2(G)≤ 7;(2)如果4 ≤Δ(G)≤7,那么 χ2(G)≤Δ(G)+5;(3)如果Δ(G)≥ 8,那么 χ2(G)≤[Δ(G)]+1.并且这个猜想至今仍然未被完全证明.图G的一个映射φ:V(G)→{0,1,2,...,k},对于图G中的任意的两个顶点u和v,当 d(u,v)=1 时,|φ(u)-φ(v)| ≥ 2;当 d(u,v)=2 时,|φ(u)-φ(v)|≥1,这时我们就称图G有一个L(2,1)-标号.使得图G有一个L(2,1)-标号的最小的k称为图G的L(2,1)-标号数,用λ2,1G)表示.对于k-L(p,1)-可选的图,当p=2时,图的kk-L(2,1)-可选问题是比图的L(2,1)-标号问题更困难的一种染色.因为L(2,1)-标号要求每个顶点的可选颜色的列表都是{0,1,2,...,k},而k-L(2,1)-可选的每个顶点的可选颜色列表是任意的满足|L(v)|≥k的,因此λ2,1(G)+1≤χ2,1l(G).本文共分为四章:第一章我们主要介绍平面图的k-L(p.1)-可选性及其背景,给出了本文中用到的基本术语与符号,列出了本文中的主要结果.第二章我们拓展了卜月华与商春慧[List 2-distance coloring of planar graphs without short cycles,2016]的一个结果:g(G)≥5,Δ(G)≥ 12 的平面图 G 是(Δ+6)-L(1,1)-可选的.我们证明了g(G)≥ 5,Δ(G)≥ 30的平面图G是(Δ+5)-L(1,1)-可选的.第三章我们改进了卜月华和严晓燕[List 2-distance coloring of planar graphs,2015]的一个结果:g(G)≥ 5,Δ(G)≤5的平面图G是13-L(1,1)-可选的.我们证明了 g(G)≥ 5,Δ(G)≤5 的平面图 G 是 12-L(1,1)-可选的.第四章我们证明了 g(G)≥ 6,Δ(G)≥ 15的平面图G是(Δ+6)-L(2,1)-可选的.
其他文献
随着经济的迅速发展,环境保护和资源限制已然变成谋求发展与扩张的企业不容忽视的难题。在愈发严格的环境保护法律法规的制约条件中,企业的各项环境风险不断增加,随之而来的环境成本也呈上升趋势。似乎只注重末端处理的传统环境成本管理方法已不再满足当今企业的环保需求。倘若继续使用这种忽略环境成本产生的传统环境成本管理方法,意味着放弃了污染防治以及过程控制的效果,就会导致环境成本失控现象,这并不利于企业的可持续发
随着云技术与互联网技术的愈发成熟,传统的呼叫中心开始向以云计算为基础的联络云呼叫中心发展。联络云呼叫中心的后台模块非常复杂,为了便于企业实现后期项目的迅速扩展和减少维护的工作量,将联络云系统中的核心模块分成公共服务模块和非公共服务模块。公共服务模块指的是项目在不同的应用场景中需要适配不同业务需求的模块,从而使联络云系统每次适配不同的项目只需要修改公共服务模块的内容从而完成项目的对接,减少系统核心模
网络评论是当今人们发表观点的重要载体,人们在评论时经常对多个方面表达观点。网络评论的属性级情感分析是一个细粒度的工作,能够挖掘出网络评论中包含的各个观点和对观点的情感。本文的目标是挖掘出评论句子包含的各个评价对象和相关的观点内容,并对每个评价对象所蕴含的情感极性进行分类。本文将该情感分析工作分为以下两步实现:(1)基于Tree-LSTM+CRF的属性级情感元素抽取研究。该部分要对网络评论进行属性级
长期以来,陕西榆林地区矿井普遍采用刀柱式或房柱式开采法,致使煤炭资源采出率极低,浪费了大量的煤炭资源。为此,本文研究提出一种新型采煤方法——窄条带膏体充填开采,即:将工作面分为若干窄条带分轮(本文以四轮为例)依次采出并进行采空区膏体充填的一种采煤方法。论文以榆林白鹭煤矿水体下压煤开采为工程背景,提出窄条带膏体充填开采的方法,阐述了窄条带膏体充填的开采-充填作业流程,模拟研究分轮开采过程中各阶段覆岩
代孕是有孕育能力的女性有目的性的打算将生育后的孩子交于他人的受孕。一般而言,该女性为不能自行受孕的夫妇(又称为委托夫妇)孕育宝宝。然而,代孕作为一项人工辅助生殖技术
金融危机对世界各国的经济建设造成了冲击,在这样的发展环境中,新造船舶数量不断增加,航运运价指数一直没有得到明显提升,再加上国际原油价格大幅增长,航运公司需要承受较高的燃油成本,航运业在发展道路上充满了荆棘。在这样的宏观环境中,各大燃油公司的业务发展陷入了困境之中。在依靠货物品质和完善的物流体系的竞争空间越来越小的情况,各大燃油公司想要提升自身竞争力,需要以自身资源为导向,制定合理的竞争战略。本文以
随着中国社会经济的快速发展,庞大的人口基数带动汽车保有量迅猛增加,目前我国仍然是全球最大的单一汽车市场。中国汽车产业的迅猛发展,体现出人们生活水平不断提高,中国汽车后市场的形成也是在汽车产业不断发展中诞生的。随着互联网的发展,互联网产业已经应用于人们生活的方方面面,把庞大体系汽车后市场业务与互联网进行融合,推动汽车后市场互联网化。当前,门店维修的服务模式已不能适应市场需求,便捷高效的汽车维修保养预
随着现代社会的飞速发展,人们对高性能处理器的需求越来越大;同时得益于电子技术与半导体工艺的不断进步,高性能处理器的设计规模和复杂度也快速增长。面对日益复杂的处理器功能及结构,为了保证工作的高效率和高可靠性,验证在研发工作中变得越来越重要。现如今,技术成熟且使用最为广泛的软件验证具有灵活、可视性强及可复用等诸多优点。但面对越来越复杂的处理器系统及越来越短的设计周期,其相较于基于FPGA的原型验证技术
改革开放四十多年以来,伴随着市场经济的空前发展,我国的城市化进程不断加快,取得了举世瞩目的成就。但是,城市不计成本的快速发展,导致了城市社会矛盾及“城市病”越发突出,给城市规划管理带来了难度。长期以来,我国的城市规划管理模式大致沿袭着以政府为主导的模式。这种以政府为中心的管理模式在城市建设的前期发挥了维护社会稳定、集中财力物力人力的重要作用。但随着经济、社会环境的变化,公民的权利意识开始觉醒,传统
固定化酶虽解决了游离酶分离困难、生产成本高、难以重复回收和利用等问题,但目前,寻找合适的固定方法,设计具有优异合成性能和可控性的载体以及优化应用工艺仍是该领域的研究重点。石墨烯材料具有优良的化学稳定性、良好的生物相容性、较高的机械强度和较大的比表面积,并且具有疏水性和亲脂性,是固定化酶载体的优良选择,并可进一步应用于油水分离及催化油脂水解。而甲壳素分子多孔网状结构且分子中丰富的羟基和氨基可以协助戊