论文摘要
图的染色问题是图论中研究的重要问题之一,起源于著名的”四色猜想”问题.图的染色不仅在离散数学,化学,计算机等领域有重要的作用,而且在现实生活中应用也非常广泛.图G的一个[k]-全染色是一个映射f:V（G）∪ E（G）→[k]={1,2,…,k}使得在V（G）∪E（G）中的任意一对相邻或相关联的元素染上不同的颜色.令f[u]表示点u的颜色和所有与点u相关联的边的颜色所组成的集合.图G的一个[k]-全染色被称作是Smarandachely邻点可区别的,如果对于G中任意一条边uv,都有|f[u]f[v]≥ 1并且|f[v]f[u]|≥1成立.我们将所用的最少颜色数k称为图G的Smarandachely邻点可区别全色数,记作Xsat（G）.本文根据外平面图的结构特点,主要运用了分析法和归纳法,以及移色,换色和抽象法等技巧研究了外平面图的Smarandachely邻点可区别全色数问题,一共分为三章.第一章引言首先介绍了研究背景,基本的概念以及关于邻点可区别全染色和Smarandachely邻点可区别全染色的研究成果,最后文章中给出了关于外平面图的Smarandachely邻点可区别全色数的几个结论.第二章分别研究了最大度为3,4,5的2-连通外平面图的Smarandachely邻点可区别全色数,证明了:如果G是一个△（G）≤ 3的2-连通外平面图,则χsat（G）≤ △（G）+3;如果G是一个△（G）=4或5的2-连通外平面图,则χsat（G）≤△（G）+4.第三章研究了外平面图的Smarandachely邻点可区别全色数,并给出了χsat（G）的上界不超过2A（G）;进一步地,如果 △（G）≥7,则 Xsat（G）≤ 2△（G）-1.
论文目录
文章来源
类型: 硕士论文
作者: 李春梅
导师: 王治文
关键词: 邻点可区别全色数,外平面图,连通图,有向图
来源: 宁夏大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 宁夏大学
分类号: O157.5
DOI: 10.27257/d.cnki.gnxhc.2019.000613
总页数: 44
文件大小: 2613K
下载量: 20
相关论文文献
- [1].双外平面图的点染色[J]. 枣庄学院学报 2013(05)
- [2].最大外平面图和最大平面图的性质[J]. 高等数学研究 2013(04)
- [3].双外平面图点染色的一个结果[J]. 科技信息(学术研究) 2008(27)
- [4].2-外平面图的无圈边色数[J]. 浙江师范大学学报(自然科学版) 2011(04)
- [5].2-外平面图的无圈边色数[J]. 数学研究 2012(01)
- [6].两类几乎外平面图的双约束边色数[J]. 济南大学学报(自然科学版) 2009(03)
- [7].小直径二连通外平面图的彩虹连通数（英文）[J]. 数学进展 2018(03)
- [8].Δ(G)≤3的2-连通外平面图的Smarandachely 邻点可区别全色数[J]. 大学数学 2019(03)
- [9].类比法在图染色中的应用[J]. 考试周刊 2018(08)
- [10].一类5-正则外平面图的亏格分布[J]. 应用数学学报 2015(05)
- [11].极大外平面图谱半径的上界[J]. 西南师范大学学报(自然科学版) 2014(02)
- [12].外平面图的邻点可区别Ⅰ-全染色（英文）[J]. 数学季刊(英文版) 2017(04)
标签：邻点可区别全色数论文; 外平面图论文; 连通图论文; 有向图论文;