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

关于图的可选择性与唯一列表可染图研究

作　者: 申玉发
导　师: 何文杰
学　校: 河北师范大学
专　业: 基础数学
关键词: 列表染色 k-可选择图选择数 k-边-可选择图边-选择数色-可选择图 Ohba猜想完全多部图 (k,l)-可选择图 (k,l)-边-可选择图可平面图唯一列表染色唯一k-列表可染图 M(k)性质
分类号: O157.5
类　型: 博士论文
年　份: 2006年
下　载: 79次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究列表染色的若干问题,包括图的色-可选择性和Ohba猜想、某些平面图的（k,l）-可选择性和（k,l）-边-可选择性,以及图（尤其是完全多部图）的唯一列表可染性。如果图G满足Ch（G）=x（G）,则称G是色-可选择的。关于图的色-可选择性,2002年Ohba[71]给出猜想:如果图G满足|V（G）|≤2x（G）+1,则G是色-可选择的。容易发现Ohba猜想成立当且仅当其对完全多部图成立,但是对完全多部图Ohba猜想被验证的情况只有图K_{3*2,2*（k-3）,1}、K_{3,2*（k-1）}和K_{t+3,2*（k-t-1）,1*t}。本文证明:完全多部图K_{t+2,3,2*（k-t-2）},1*t)（t=2,3,4;k≥t+2）是色-可选择图。因此得到,对图K_{t+2,3,2*（k-t-2）,1*t}（t=1,2,3,4;k≥t+2）及其所有k-色子图Ohba猜想成立。对独立数最大为3的图,2004年Ohba[72]证明了Ohba猜想的一个较弱的形式:如果图G满足|V（G）|≤2x（G）,且G的独立数最大为3,则G是色-可选择的。在此我们证明:若r≤t+1且k≥r+t,则Ch(K_{3*r,2*（k-r-t）,1*t})=x(K_{3*r,2*（k-r-t）,1*t})=k。此结果表明:在如上Ohba的论断中,条件|V（G）|≤2x（G）可以换成|V（G）|≤2x（G）+1。即对每个独立数最大为3的图及其所有x（G）-色子图Ohba猜想成立。图的（k,l）-可选择性问题是图的k-可选择性问题的推广。关于图的（k,l）-可选择性,1979年Erd（?）s等人[26]提出了如下猜想:对任意整数m≥1,每一个（k,l）-可选择的图G也是（km,lm）-可选择的。1996年Tuza和Voigt[94]证明了这个猜想在k=2和l=1的情形是正确的,但是对任意的（k,l）验证这个猜想的工作还相差甚远。本文证明:对任意整数m≥1,每一个没有t-圈（t=3,4,5或6）的平面图是（4m,m）-可选择的。这一结果推广了分别由Lam等人[65]、由Wang和Lih[106]、由Fijav（?）等人[28]给出的如上图都是4-可选择的结果。另一方面,我们还证明:如果一个平面图G不包含t-圈（t=3,4,5或6）且△（G）≠4,

全文目录

插图目录  9-11
摘要  11-13
ABSTRACT  13-15
第一章引言  15-29
  §1.1 综述  15-24
  §1.2 基本概念  24-29
第二章图的色-可选择性与Ohba猜想  29-61
  §2.1 关于图是色-可选择的若干猜想  30-31
  §2.2 Ohba猜想的等价形式及其被验证的图类  31-33
  §2.3 对图K_(t+2，3，2*(k-t-2)，1*t)(t=2，3，4)Ohba猜想成立  33-51
    §2.3.1 命题和引理  33-36
    §2.3.2 图K_(4，3，2*(k-4)，1*2)(k≥4)的色-可选择性  36-41
    §2.3.3 图K_(5，3，2*(k-5)，1*3)(k≥5)的色-可选择性  41-45
    §2.3.4 图K_(6，3，2*(k-6)，1*4)(k≥6)的色-可选择性  45-51
  §2.4 对独立数最大为3的图Ohba猜想成立  51-61
第三章某些平面图的(k，l)-(边-)可选择性  61-81
  §3.1 图的(k，l)-可选择性猜想  61-63
  §3.2 没有t-圈(t=3，4，5或6)的平面图的(k，l)-可选择性  63-66
    §3.2.1 命题和引理  63-64
    §3.2.2 主要结果  64-66
  §3.3 图的边-可选择性猜想  66-68
  §3.4 没有t-圈(t=3，4，5或6)的平面图的(k，l)-边-可选择性  68-81
    §3.4.1 引理和命题  69-74
    §3.4.2 主要结果  74-81
第四章完全多部图的唯一列表染色  81-111
  §4.1 关于唯一列表可染图的特征化和一个开放问题  82-83
  §4.2 U2LC图特征化定理证明的简化  83-91
    §4.2.1 圈具有M(2)性质的一个简单证明  83-85
    §4.2.2 U2LC图特征化定理中必要性的一个简化证明  85-91
  §4.3 U3LC完全多部图K_(r，s，t)和K_(1*r，s)的若干性质  91-96
    §4.3.1 U3LC完全三部图K_(r，s，t)的性质  92-94
    §4.3.2 U3LC完全多部图K_(1*r，s)的性质  94-96
  §4.4 关于Ghebleh和Mahmoodian开放问题的研究  96-111
    §4.4.1 完全多部图K_(2，2，r)(r=4，5，6，7，8)具有M(3)性质  96-101
    §4.4.2 完全多部图K_(1*5，4)和K_(1*4，4)具有M(3)性质  101-107
    §4.4.3 完全多部图K_(1*4，5)具有M(3)性质  107-110
    §4.4.4 结论  110-111
参考文献  111-119
索引  119-121
攻读博士学位期间撰写的学术论文  121-123
致谢  123

关于图的可选择性与唯一列表可染图研究

内容摘要

全文目录

相似论文