论文部分内容阅读
分数着色是顶点着色的一个推广,对于某些具体问题,它能更好地刻画解决。分数色数作为图的重要参数之一,是非常具有研究价值的。 文中首先给出图的分数色数的定义,研究了简单图的和运算、正规积运算及联运算的分数色数,并且根据顶点可迁图的分数色数研究循环图、圈的幂的分数色数及其积运算的分数色数。从而得到各个运算的一个比较严格的上界,进而完善图的运算的分数色数与其因子的分数色数之间的关系,得到求图的和运算、正规积运算、联运算的分数色数的比较精确的计算方法。 然后将分数着色推广到有限超图中,研究其在有限超图中的性质。文中主要研究了超图的奇偶圈、线性超图及其相关的对偶超图、2-分图、线图、关联图、Hpq(r)超图、r-一致循环超图等特殊超图的分数色数;并确定了无环超图的积运算的色数与因子的分?数色数之间的关系及超图的字典积运算的分数色数与因子的分数色数间的关系。 最后用概率方法证明了分数色数的一个上界的成立,同时得到一个构造图的分数着色的算法。