图四类染色及其色数估计.doc

分类  O157.5  密级 硕士学位论文 图的四类染色及其色数估计 孙春虎 导师姓名 职称: 刘信生 教授 专 业 名 称:运 筹 学 与 控 制 论 论 文 答 辩 日 期: 2012 年 5 月  研 究 方 向: 图 论 及 其 应 用 学 位 授 予 日 期: 2012 年 6 月 答辩委员会主席: 评  阅  人: 二○一二年五月 硕士学位论文 M.D.Thesis 图的四类染色及其色数估计 Four kinds of Coloring of Graphs and its Chromatic Number Estimation 孙春虎 Sun Chunhu 数学与信息科学学院 College of Mathematics and Information Science 目录 独创性声明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  i 摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 符号说明. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 第一章 前 言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1 第二章 预备知识 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 第三章 图的星边星-全染色 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 § 3.1 特殊图的星边星-全染色. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  6 § 3.2 用概率方法给出一般图的星边星-全色数的上界 . . . . . . . . . . . . . . . . . . . . . . . . . . 13 第四章 图的D(2)-点可区别星全染色. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 § 4.1 特殊图的D(2)?点可区别星全染色 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 § 4.2 用概率方法给出一般图的D(2)?点可区别星全色数的上界 . . . . . . . . . . . . . . . . 21 第五章 有向图的星边弧染色. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 § 5.1 特殊有向图的星边弧染色 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 § 5.2 用概率方法给出满足一定条件的有向图的星边弧色数的上界 . . . . . . . . . . . . . 28 第六章