论文部分内容阅读
图的关联着色是从关联集I(G)到颜色集合C的一个映射σ,使得G中任何两个相邻关联具有不同的象,若σ:I(G)→C是G的一个关联着色且|C|=k,k是一个正整数,则称G是k-可关联着色的,使得σ是G的一个k-关联着色的最小的k值称为G的关联色数,记为Xi(G),即Xi(G)=min{|C‖σ:I(G)→C是G的关联着色}. 图的d-距离关联着色是关联着色的一个推广.图G的d-距离关联着色是从关联集I(G)到颜色集合C(d)的一个映射σ,使得G中任何两个d-距离相邻的关联具有不同的象.若σ:I(G)→C(d)是G的一个k-d-距离关联着色且|C(d)|=k,k是一个正整数,则称G是k-可d-距离关联着色的,是G的一个k-d-距离关联着色.使得σ是G的一个k-可d-距离关联着色的最小的k值,称为G的d-距离关联色数,记为Xi(d)(G),即Xi(d)(G)=min{|C(d)‖σ:I(G)→C(d)是G的一个d-距离关联着色}. 本文研究了若干图的d-距离关联着色,具体安排如下: 在第一章中,给出了d-距离关联着色和d-距离关联色数的概念和基本性质. 在第二章中,通过运用反证、穷染等方法,研究了路,圈,星,扇,轮,完全图,完全二部图的1-距离关联色数.随后,给出了皇冠图,广义皇冠图,图Ln,k,图Ln的概念,以及它们的1-距离关联色数. 在第三章中,证明了路,圈,树,星,扇,轮,完全图,完全二部图,Ln,k的3-距离关联色数. 论文的第四章主要研究了d>3时路,圈,星,扇,轮的d-距离关联色数.