文档介绍：南通大学本科生毕业设计（论文）开题报告
学生姓名
刘琴 学号 0902012001 专业 数学与应用数学
课题名称
Mycielski图的b染色问题初探
阅读文献
情 况
国内文献 4本
开题日期
国外文献 3篇
开题地点
钟秀校区
一 文献综述与调研报告：（阐述课题研究现状及发展趋势，本课题研究的意义和价值、参考文献）
设G是一个无环图，G的顶点正常*染色是指*种颜色1,2,.../对于G的各顶点的一种分 配，使得任二相邻的顶点被染上不同的颜色，换句话说，G的顶点正常上染色是一个映射 勿：％）T {1,2,,使导勿t（z'）是独立集或空集。=1,2,.../）。1999年，Iz'vzVzg 和Manlove 在图的a染色数的概念的基础上提出了图的力染色数的概念。一个图G的正常k染色中，如果每一 个颜色类中都至少存在一个顶点,使其在其他的*-1个颜色类中都至少有一个邻居,则称这样的正 常*染色为b染色,这样的顶点为b染色顶点。一个图G的b染色数是使图G满足b染色的最大的 正整数k，使得用*种颜色能够对G进行b染色，用b（G）来表示。living和Manlove证明了，对于
一个任意的图G来说,确定其b染色数c（G）是一个NPC问题。2002年Kouider和Ma服。研究 了乘积图的力染色问题。2006年K。”诙r和Za ker对于给定最小团划分的图和二部图给出了 b 色数的上界。2010年，吕闯在5染色和b连续概念的基础上提出了 b边染色和b边连续的概念。 如果对于任意的正整数*, /（G）＜k＜（p'（G）, MJ'以用左种颜色对图G进行力边染色，那么就 说图G是边连续的。
由某个不含三角形的k***Gk构造不含有三角形的* +1***Gk+l的构造方法称为
Mycielski构造，构造方法是:设G*的顶点集为[ul,u2,...,un],给添加〃+ 1个新顶点
vx,v2,...,vn,v,每个v；与"，.在G»中的所有临边连边，同时也与v连边，i = 1,2,。而构造出的
图G?称为Mycielski图。
图论是数学的一个分支，是近年来发展迅速的一门新兴学科。图论的应用十分广泛，在运筹 学、应用数学、计算机科学与技术、信息科学、生命科学、自动控制、工程建设以及能源、交通、 电子、通信、化学、物流、管理、社会科学等众多领域都能找到其应用范例。而染色问题是图论 中十分活跃的研究课题，有着深刻而丰富的理论结果和广泛的实际应用，其理论和方法在离散数 学中占有重要地位。由于染色问题反映了广泛而又深刻的实际背景，它的研究带动了图论的发展, 从而推动科技的发展。
3 .参考文献
[M].北京：高等教育出版社，2010, 2-213
-边染色数及b-边连续性研究[J].吉林化工学院学报,2010,第27卷04期：91-94
李敬文，,2003,第22卷04期：1-4
李敬文，[J].陕西师范大学学报,2002. 30(增)：18 20
Chang G J, Huang L, Zhu X.