关于几类图的分数色数-运筹学与控制论专业论文.docxVIP

THE FRACTIONAL CHROMTIC NUMBERS OF SOME GRAPHS A Dissertation submitted in fulfillment of the requirements of the degree of MASTER OF SCIENCE from ShanDong University of Science and Technology by Wang Caihong Supervisor: Associate Professor Liu Xikui College of Information Science and Engineering May 2008 声 明 本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公 认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于 其它任何学术机关作鉴定。 硕士生签名： 日 期： AFFIRMATION I declare that this dissertation, submitted in fulfillment of the requirements for the award of Master of Science in Shandong University of Science and Technology, is wholly my own work unless referenced of acknowledge. The document has not been submitted for qualification at any other academic institute. Signature: Date: 山东科技大学硕士学位论文摘要 山东科技大学硕士学位论文 摘要 摘 要 分数着色是顶点着色的一个推广，对于某些具体问题，它能更好地刻画解决。分数 色数作为图的重要参数之一，是非常具有研究价值的。 文中首先给出图的分数色数的定义，研究了简单图的和运算、正规积运算及联运算 的分数色数，并且根据顶点可迁图的分数色数研究循环图、圈的幂的分数色数及其积运 算的分数色数。从而得到各个运算的一个比较严格的上界，进而完善图的运算的分数色 数与其因子的分数色数之间的关系，得到求图的和运算、正规积运算、联运算的分数色 数的比较精确的计算方法。 q然后将分数着色推广到有限超图中，研究其在有限超图中的性质。文中主要研究了 超图的奇偶圈、线性超图及其相关的对偶超图、 2 ? 分图、线图、关联图、 Hp (r) 超 图 、 q r? 一致循环超图等特殊超图的分数色数；并确定了无环超图的积运算的色数与因子的分 数色数之间的关系及超图的字典积运算的分数色数与因子的分数色数间的关系。 最后用概率方法证明了分数色数的一个上界的成立，同时得到一个构造图的分数着 色的算法。 关键词：分数着色；分数色数；积运算；和运算；正规积运算；超图；概率方法 ABSTRACT The fractional chromatic number of a graph is a variation of the chromatic number. It can provide a better model for some special problems. As an important parameter, the chromatic number of the graph has the values of studying. Firstly, the definition of fractional chromatic number is given in this paper. The fractional chromatic numbers of sum of graphs, normal product of graphs and join of graphs are studied. In terms of the fractional coloring of the vertex- transitive graph, the fractional chromatic numbers of circular graphs, powers of cycles and the direct product of theme are studied. Then the upper bound and lower bound of the fractional chromatic numbers of the algorithms of graphs