距离图的着色和循环图的星极性

论文摘要

假设S是度为δ的度量空间μ的子集,D是一个正实数集,则距离图G（S,D）具有顶点集S以及距离集D,且满足:对（?）x,y∈S,x,y相邻当且仅当δ（x,y）∈D.图G的一个k-顶点着色是指k种颜色对于G的所有顶点的一个分配;如果任意两个相邻顶点都分配到不同的颜色,则称该着色是正常的.当G有一个正常k-顶点着色时,称G是k-顶点可着色的.G的色数是使G为k-可着色的七的最小值,通常用x（G）表示.图G的圆色数是图G的色数x（G）的一个自然推广.假设p和q是正整数且p≥2q,图G的（p,q）一着色是一个映射c:V（G）→{0,1,2,…p-1},使得对于任意的边xy∈E（G）,都有‖c（x）-c（y）‖p≥q,其中‖a‖p=min{a,p-a}.图G的圆色数Xc（G）是G的存在的（p,q）-着色中p/q的最小值.图的一般色数的另一个推广是图的分数色数,它的定义如下:给定一个图G（V,D）,用I（G）表示图G的所有独立集构成的集合,如果存在一个从I（G）到区间[0,1]的函数c,使得对（?）x∈V（G）,都有∑x（?）（?）（G）c（I）≥1,我们就称函数c为图G的一个分数着色.该分数着色的值为∑x（?）（?）（G）c（I）,并称Xf（G）=inf{∑（?）（G）c（I）}为图G的分数色数.一个图G称为是星极的当且仅当图G的圆色数等于它的分数色数,即Xc（G）=Xf（G）.令p是一个正整数,集合S={0,1,2,…,p-1}满足若i∈S即有p-i∈S,为简便起见,可以把p-i表示为-i。则循环图G（p,S）具有顶点0,1,2,…,p-1,且任意两个顶点i、j相邻当且仅当i-j∈S,其中减法对p取模.本文首先介绍了图的色数、圆色数和分数色数之间的关系,再利用构造法、反证法、分解法、穷染法等方法,讨论了一类整数距离图G(Z,Dm,k,k+1,k+2,k+3(其中Dm,k,k+1,k+2,k+3={1,2,…,m}-{k,k+1,k+2,k+3})的色数、分数色数,再利用该图的色数和分数色数求出了它的圆色数.此外,还介绍了有关星极图和循环图的一些已有结论,并且利用这些结论证明了几类循环图具有星极性质.

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 绪论
• 1.1 图的基本知识
• 1.2 距离图的起源及其研究现状
• 1.3 本文的主要研究内容与安排
• m,k,k+1,k+2,k+3的着色'>2 距离图G(Z,D_{m,k,k+1,k+2,k+3}的着色
• m,k,k+1,k+2,k+3的分数色数'>2.1 距离图G(Z,D_{m,k,k+1,k+2,k+3}的分数色数
• m,k,k+1,k+2,k+3的色数'>2.2 离图G(Z,D_{m,k,k+1,k+2,k+3}的色数
• m,k,k+1,k+2,k+3的圆色数'>2.3 离图G(Z,D_{m,k,k+1,k+2,k+3}的圆色数
• 3 循环图的星极性
• 3.1 基本概念及预备定理
• 3.2 主要结果及其证明
• 4 结束语
• 致谢
• 参考文献