平面图的r-hued染色

发布时间：2017-10-09 09:34

  本文关键词：平面图的r-hued染色

  更多相关文章： 平面图 极小反例 差值转移 勒贝格公式

【摘要】：一个有序对G=(V, E)称为一个无向图,其中V和E通常是有限集合.V中的元素称为图G的顶点,E是由V中不同元素的无序对组成的集合,E中的元素称为图G的边.我们通常用V(G)和E(G)来表示图G的顶点集和边集.一个图G称为是平面的当且仅当它可以画在平面上,使得它的任何一条边不与另外一条边交叉.对于正整数k,r.令k={1,2,…k}.如果c:V(G)→k,V'(?)V(G),那么c(V')={c(v)|u∈V')图G的(k,r)染色是这样一个映射c:V(G)→k,满足下列两个条件：(C1)对于每条边uv∈E(G),c(u)≠c(v);(C2)对于每个点v∈V(G),|c(NG(v))|≥min{dG(v),r}.条件(C2)经常被作为r-hued条件.对于整数k,r0,图G的(k,r)染色是一个正常k染色,使得对于每一个度数为d(v)的点v,v至少表现min{d(u),r}种颜色,这样的染色,我们称之为r-hued染色,图G的r-hued染色数,记作Xr(G).是使图G存在(k,r)染色的最小的k值r-hued染色是图的点染色的推广本学位论文主要研究了围长至少为5的平面图的r-hued染色以及一般平面图的3-hued染色.第一章,介绍研究领域的相关发展背景,研究现状和本文所要用到的基本概念.第二章,证明了围长至少为5的平面图的r-hued染色的相关结果：当3≤r≤7时,且图G是围长至少为5的平面图,则x,(G)≤r+11特别的,当r=3,4,5,6时,分别有x3(G)≤10,x4(G)≤11,x5(G)≤12,x6(G)≤13.第三章,给出了一般平面图的3-hued染色的结果,即若图G是一个平面图,则X3(G)≤12.第四章,对本文的研究结果作了简单的总结并做了进一步的展望.
【关键词】：平面图 极小反例 差值转移 勒贝格公式
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 致谢4-5
• 摘要5-6
• Abstract6-10
• 变量注释表10-11
• 1 绪论11-15
• 1.1 研究背景11-12
• 1.2 基本概念12
• 1.3 研究现状12-15
• 2 围长至少为5的平面图的r-hued染色15-27
• 2.1 几个结构引理15-24
• 2.2 主要结果24-27
• 3 一般平面图的3-hued染色27-33
• 3.1 主要结果28-33
• 4 总结与展望33-34
• 参考文献34-37
• 作者简历37-40
• 学位论文数据集40

【相似文献】

中国硕士学位论文全文数据库 前1条

1 李卫奇;平面图的r-hued染色[D];中国矿业大学;2016年

，

本文编号：999459