学位论文 > 优秀研究生学位论文题录展示

平面图的边列表染色和线性染色

作　者: 姚潇彦
导　师: 王应前
学　校: 浙江师范大学
专　业: 应用数学
关键词: 平面图边列表染色线性染色最大度围长
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 14次
引　用: 0次
阅　读: 论文下载

内容摘要

一个有序对G=(V,E)称为一个无向图,其中V是一个有限集合,E是V中的不同元素的无序对的集合.V中的元素叫做图G的顶点,E中的元素叫做图G的边.通常用V(G),E(G)分别表示图G的顶点集合与边集合.没有重边和环的图叫做简单图.图G的一个k-边染色是一个映射φ：E(G)→{1,2：…,k｝,其中k是整数.若映射φ还满足对于G中的每一对相邻边e和e’,有φ(e)≠φ(e′),则称这个k-边染色是正常的.如果G有一个正常的k-边染色,则称G是k-边可染的.G的边色数χ′(G)是使得G是k-边可染的最小的整数,称L为图G的一个边列表,如果它给每条边e∈G,一个颜色集合L(e),若有一个正常的边染色φ,使得每一条边e满足φ(e)∈L(e)则称G是L-边可染的,或称φ是G的一个L-边染色.如果对任意表L和每条边e∈E(G),都有|L(e)|≥k,且G是L-边可染的,则称G是k-边可选的.G的边列表色数χl′(G)是使得G是k-边可选择的最小的非负整数k.类似地可定义单独染顶点和同时染顶点和边的G的点列表色数χl(G)和全列表色数χl″(G).由定义可直接得到χl′(G)≥χ′(G)≥Δ(G)和χl″(G)≥χ″(G)≥Δ(G)+1.如果图G的一个正常顶点染色c满足染任意两种颜色的顶点集合导出的子图是一个线性森林,即一些点不交的路的并,则称这个正常点染色c为图G的线性染色.图G的线性色数,是指图G的所有线性染色中使用的最少颜色的个数,用lc(G)表示.本文主要讨论平面图的边列表染色和线性染色问题.对前人的一些研究结果进行改进和补充.在第一章中,给出本文所用到的基本概念,介绍相关领域的背景和研究现状,呈现本文的主要结果.第二章中,主要证明了关于平面图的边列表染色的研究结果：最大度为6且不含4-圈和7-圈的平面图是△-边可选的,(△+1)-全可选的；最大度为5且不含4,6,8-圈的平面图是△-边可选的,(△+1)-全可选的.第三章中证明了关于平面图的线性染色的研究结果：设G是一个平面图,若G满足下面条件之一,则lc(G)=[Δ(G)/2]+1(1)△(G)≥11且g(G)≥7(2)△(G)≥5且g(G)≥9

全文目录

摘要  2-4
ABSTRACT  4-6
目录  6-7
1 绪论  7-12
  1.1 基本概念  7-8
  1.2 边列表染色的研究概况  8-9
  1.3 线性染色的研究概况  9-10
  1.4 本文的主要结果  10-12
2 平面图的边列表染色  12-25
  2.1 最大度为6的平面图  12-18
  2.2 最大度为5的平面图  18-25
3 线性染色  25-44
参考文献  44-47
在学期间的研究成果及发表的论文  47-48
致谢  48-50

平面图的边列表染色和线性染色

内容摘要

全文目录

相似论文