平面图的弱边面染色

发布时间：2020-05-31 17:57

【摘要】：令G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.图G的一个正常k-边面染色是指存在一个映射π:E(G)∪(G)→ {1,2,…,k}满足:若边e1与边e2相邻,则π(e1)≠ π(e2);若面f1与面f2相邻,则π(f1)≠ π(f2);若边e与面f相关联,则π(e)≠ π(f).如果G有一个正常k-边面染色,那么称G是k-边面可染的.图G的边面色数xef(G),定义为使得G是边面k-可染的最小的正整数k的值.这个概念最早由Jucovic和Fiamcik在1970年前后分别独立提出.在正常边面染色定义的基础上,2016年,Fabrici等人首次提出了弱边面染色的概念.图G是弱边面k-可染的是指存在一个映射π:E(G)∪F(G)→ {1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.这里,我们称两条相邻边e1和e2是面相邻的当它们关联同一个面且在该面的边界上连续出现时.平面图G的弱边面染色数是指G是弱边面k-可染的正整数k的最小值,用xef(G)表示.Fabrici等人证明了每个无环且无割边的连通平面图是弱边面6-可染的.同时,他们猜想:每个无环且无割边的连通平面图是弱边面5-可染的.此猜想引起了研究者们的极大兴趣.目前为止,该猜想仍未完全解决.因此,研究该染色问题是十分有意义的.本学位论文主要围绕以上猜想加以研究.学位论文共分为四个章节,如下所示:第一章节,我们首先给出本文中所要用到的图论的基本概念,然后简述相关领域的研究现状,最后给出本文的主要结果.第二章节,第三章节以及第四章节,我们运用数学归纳方法分别研究了哈林图、极大平面图、外平面图这三类特殊的平面图.具体来讲,我们运用色延拓技巧,组合计数,颜色置换等方法证明了如下三个结果满足以上猜想,即:(1)每个哈林图都是弱边面5-可染的.(2)每个极大平面图都是弱边面5-可染的.(3)每个外平面图都是弱边面5-可染的.需要指出,以上三个结果中的上界5均是最优的.
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 刘海涛;谢建民;;关于Kneser图的一个分数染色性质[J];甘肃高师学报;2016年12期

2 刘海涛;张强;;图的点可区别的分数边染色数[J];数学的实践与认识;2017年19期

3 达文姣;任志国;;扇、轮和完全图的r(2)点色数[J];甘肃联合大学学报(自然科学版);2011年02期

4 孔静;;图乘积的分数色数[J];泰山学院学报;2011年03期

5 黎虹;刘信生;;边共色数下图的分类问题[J];长春工业大学学报(自然科学版);2011年06期

6 王艳丽;;联图的星色数[J];黑龙江科技学院学报;2011年06期

7 吕闯;;图的b-边染色数及b-边连续性研究[J];吉林化工学院学报;2010年04期

8 亢琳;杨爱民;;θ-图的对策着色和对策色数[J];中北大学学报(自然科学版);2009年01期

9 高炜;梁立;夏幼明;;两种特殊冠图的相关分数色数研究[J];西安文理学院学报(自然科学版);2009年01期

10 ;升级手机的四大误区[J];广西质量监督导报;2009年05期

相关会议论文 前1条

1 段华;陈东灵;;系列平行图的边面着色[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

相关重要报纸文章 前9条

1 家宝 摘;升级手机避免四大误区[N];电子报;2006年

2 邢剑;手机唯色[N];中国计算机报;2003年

3 吴暑明;3英寸当道 宽屏幕风靡[N];中国消费者报;2008年

4 黄绍平;LCD产业和市场新动态[N];中国电子报;2000年

5 散武 亦言 王立全 吴家丰 路边 吴家丰 千守 杜满强;科技展台[N];中国纺织报;2005年

6 红梅;松日i-Mat 掌上电脑[N];计算机世界;2003年

7 林宗辉;HDMI 1.3版面世觊觎新一代通用显示标准宝座[N];电子资讯时报;2006年

8 刘悠;细数手机六大技术欺骗[N];中国消费者报;2007年

9 然光;针尖对麦芒[N];中国计算机报;2007年

相关博士学位论文 前8条

1 王光辉;边染色图中的匹配、圈及图的圆染色[D];山东大学;2007年

2 张霞;图的f-染色和均匀边染色[D];山东大学;2007年

3 刘彬;图的点可区别染色、列表染色和线性染色[D];山东大学;2010年

4 张莹丽;图的一些极值问题研究[D];南京师范大学;2017年

5 李金波;图上几类边覆盖染色问题的研究[D];山东大学;2011年

6 周文礼;条件染色的算法与复杂性[D];南开大学;2010年

7 曹倪;图中的短圈结构及相关问题研究[D];华东师范大学;2013年

8 史永堂;Randic指标与图的若干不变量[D];南开大学;2009年

相关硕士学位论文 前10条

1 余梦蕾;平面图的弱边面染色[D];浙江师范大学;2018年

2 张家娇;一些图的r-动态染色和列表r-动态染色问题[D];天津师范大学;2018年

3 王s，

本文编号：2690243