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

图的线性染色

作　者: 李超
导　师: 王维凡
学　校: 浙江师范大学
专　业: 运筹学与控制论
关键词: 线性染色 非负特征图 围长 最大度
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 24次
引　用: 0次
阅　读: 论文下载
 

内容摘要


用G=（V，E）表示一个顶点集为V,边集为E的有限、简单无向图,{1,2,…,k}表示k个颜色的集合.G的一个正常k-染色是一个映射φV→{1,2,…,k}使得相邻的顶点接受不同的色.如果G有一个正常k-染色,则称G是k-可染的.G的色数χ（G）是使得G是正常k-可染的最小的非负整数k.如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc（G）表示,是指G的所有线性染色中所用的最少颜色的个数.1998年,Yuster[1]首先研究了图的线性染色.证明了任意图G的线性色数满足lc（G） = O(Δ?),且构造出了一类图使得lc（G）=Ω(Δ?).事实上,这个概念是图的无圈染色的一种特殊情形.无圈染色的概念是由Grunbaum[2]提出的,图G的一个无圈染色是G的一个正常染色,使得染任意两种颜色的顶点集合导出的子图是一个森林.本学位论文主要是对前人的一些研究结果的改进和扩充,对非负特征图、平面图和一些度数较小的图的的研究.设Δ（G）和g（G）分别表示图G的最大度和围长.在第一章中,我们给出本文所用到的基本概念,简述了相关领域的研究现状以及呈现了本文的主要结果.在第二章中,我们证明了下面的结果:（1）对于每一个非负特征图G,若存在一个有序对（Δ,g）∈{（13,7）,（9,8）,（7,9）,（5,10）,（3,13）}使得Δ（G）≥Δ且g（G）≥g,则lc（G）=（?）.在第三章中,我们获得了下面的结果:（1）对于每一个平面图G,若满足Δ（G）≥3且g（G）≥12或者Δ（G）≥7且g（G）≥8,则lc（G）=（?）+1.在第四章中,我们又对度数较小的图进行了研究,得到了下面两个结果:（1）若图G的最大度为4,则lc（G）≤8.（2）若图G的最大度为5,则lc（G）≤14.

全文目录


摘要  3-5
ABSTRACT  5-7
目录  7-8
一、绪论  8-13
  (一)、基本概念  8-9
  (二)、关于线性染色的研究现状  9-11
  (三)、本文的主要工作  11-13
二、关于非负特征图的线性染色问题  13-35
三、关于平面图的线性染色问题  35-51
四、关于度数较小的图的线性染色问题  51-58
  (一)、最大度为4的图的线性染色  51-54
  (二)、最大度为5的图的线性染色  54-58
参考文献  58-61
致谢  61-62
在学期间的研究成果及发表的论文  62-64

相似论文

  1. 多进制LDPC码构造方法的研究,TN911.22
  2. 基于围长搜索的LDPC码构造算法研究,TN911.2
  3. 一种改进PS-LDPC码的研究及FPGA设计,TN791
  4. 双圈图的特征值与结构参数,O157.5
  5. 二面体群上的群环的零因子图,O153.3
  6. 三次对称群上的群环的零因子图,O153.3
  7. 最大度为6的平面图的全染色,O157.5
  8. 平面图的边列表染色和线性染色,O157.5
  9. 图的临界群和染色唯一性的研究,O157.5
  10. 给定围长的图的超三限制性连通度的充分条件,O157.5
  11. R（+）M与R（？）I的零因子图,O153.3
  12. Z_n[ω]与形式三角矩阵环的零因子图,O153.3
  13. 群环的零因子图,O153.3
  14. 最大度大于等于7的平面图全染色,O157.5
  15. 树的极大独立集的计数问题,O157.5
  16. 结合最大度与最小聚类系数的复杂网络搜索策略研究,O157.5
  17. 两类图的一些极值问题研究,O157.5
  18. 图的群着色数,O157.5
  19. 基于复杂网络的P2P搜索技术研究,TP393.02
  20. 低密度校验码的围长提升研究,TN911.2
  21. 图的邻点可区别全染色和边染色,O157.5

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com