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

平面图的无圈边染色

作　者: 舒巧君
导　师: 王维凡
学　校: 浙江师范大学
专　业: 运筹学与控制论
关键词: 平面图最大度围长无圈边染色 K4-minor free图
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 42次
引　用: 0次
阅　读: 论文下载

内容摘要

给定一个图G,用E(G),Δ(G)和g(G)分别表示它的边集,最大度和围长.G的正常k-边染色是一个映射c:E(G)→{1,2,…,k)使得相邻的边染不同的颜色.无圈k-边染色是指图G的一个正常的k-边染色,使得不产生双色圈.无圈边色数a’(G)是使得G是无圈k-边染色的最小整数k.无圈边染色的概念最早是由Fiamcik(1978)提出的.Alon等人(1991)运用概率方法证明了：对任何图G有a’(G)≤64Δ(G).Molly和Reed(1998)将其改进到0’(G)≤16Δ(G).2005年,Muthu等人证明了当g(G)≥220时,a’(G)≤4.52Δ(G).2001年,Alon等人提出了以下著名的无圈边染色猜想：猜想：对任意图G,有a’(G)≤Δ(G)+2.这个猜想至今仍未得到证实,仅知道一些特殊图类满足该猜想.本文在前人工作的基础上,进一步研究了平面图的无圈边染色问题,共分4章.在第1章,我们给出所用到的基本概念,简述了相关领域的研究现状并呈现了本文的主要研究结果.在第2章,我们研究了围长至少为5的平面图的无圈边染色,证明了：对一个平面图G,如果存在(k,m)∈{(3,11),(4,8),(5,7),(8,6),(12,5)},使得Δ(G)≥k, g(G)≥m,则a’(G)=Δ(G)这改进了一些已知结果.在第3章,我们研究了围长为4的平面图的无圈边染色,证明了：每一个围长为4的平面图G有a’(G)≤△(G)+2,即无圈边染色猜想对这类图成立.在第4章,我们研究了K4-minor free图的无圈边染色,并依a’(G)=△(G)或a’(G)=Δ(G)+1完全刻画了△(G)≠4的K4-minor free图.这是对外可平面图相应结论的一个推广.

全文目录

摘要  3-4
ABSTRACT  4-6
目录  6-8
1 绪论  8-17
  1.1 基本概念  8-10
  1.2 无圈边染色的研究概况  10-16
  1.3 本文的主要结果  16-17
2 围长至少为5的平面图的无圈边染色  17-56
  2.1 几个预备引理  17-19
  2.2 围长至少为6的情形  19-41
  2.3 围长为5的情形  41-56
    2.3.1 一个结构引理  41-48
    2.3.2 无圈边染色  48-56
3 围长为4的平面图的无圈边染色  56-69
  3.1 结构引理  56-59
  3.2 主要结论及证明  59-69
4 K_4-minor free图的无圈边染色  69-82
  4.1 不可避免子构型  70-74
  4.2 Δ≠4情形的一个刻画  74-82
    4.2.1 Δ≥5  74-79
    4.2.2 Δ≥3  79-82
参考文献  82-86
致谢  86-87
在学期间的研究成果及发表的论文  87-89

平面图的无圈边染色

内容摘要

全文目录

相似论文