平面图的动态染色

发布时间：2021-05-07 11:04

　　本文仅考虑有限简单图.图G的一个正常k-染色是指映射φ:V（G）→{1,2,…,k}使得对任意的uv∈E（G）,有φ（u）≠φ（v）.对于图G的一个（k,r）-动态染色,指的是G上的一个正常k-染色φ满足对于任意的顶点v,有|φ(NG（v）|≥min{dG（v）,r}.图G的r-动态染色数χr（G）,是最小的正整数k,使得G有（kk,r）-动态染色.在2001年,Montgomery首次提出了动态染色的概念,随后越来越多的学者开始研究动态染色,由动态染色的定义可得,χ（G）=χ1（G）≤χ2（G）≤…≤χr（G）≤…≤χΔ（G）=χΔ+1（G）=…=χ（G2）,其中G2是图G的平方图.我们可以看到动态染色其实是正常染色的推广.在2011年,类似Wegner猜想,赖虹建等人给出了的平面图上r-动态染色猜想:对于平面图G,若1 ≤r≤3,那么χr（G）≤r+3;若3≤r≤7,那么χr（G）≤r+5;若r≥8,那么χr（G）≤[3r/2]+1.围绕这个猜想,本学位论文研究了平面图的动态染色的一些结论.第一章主要概述了动态染色的研究现状和一些图的基本概念.第二章研究了缺少某些特定短圈的平面图G... 

【文章来源】：浙江师范大学浙江省

【文章页数】：52 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 基本概念
    1.2 动态染色的研究现状
    1.3 主要结果
第二章 缺少某些短圈的平面图的动态染色
    2.1 定理2.1的证明
    2.2 定理2.2的证明
第三章 围长至少为5的平面图的动态染色
参考文献
攻读学位期间取得的研究成果
致谢


【参考文献】：
期刊论文
[1]可平面图的r-hued染色（英文）[J]. 朱海洋,顾毓,盛景军,吕新忠.  应用数学. 2016(02)
[2]On 3-Hued Coloring of Graphs[J]. Ting LIU,Lei SUN.  Journal of Mathematical Research with Applications. 2014(01)

博士论文
[1]L（2,1）-标号和r-动态染色[D]. 朱俊蕾.浙江师范大学 2019

硕士论文
[1]平面图的r-hued染色[D]. 李卫奇.中国矿业大学 2016



本文编号：3173283