一类距离图的分数色数.pdfVIP

第43卷第6期 山东大学学报(理学版) 2008年6月 V01．43No．6 of Jun．2008 JournalShandong Science) University(Natural 一类距离图的分数色数 刘西奎，赵秉清，王彩虹，薛圣伟 (山东科技大学信息科学与工程学院，山东青岛266510) 数色数，以及当2蠡≤m，2k+5时c(z，D册^…m2m3)的色数。 关键词：距离图；分数色数；色数 中图分类号：0157．5 文献标志码：A numberofoneclassofdistance Fractionalchromatic graphs LIU Xi—kui，ZHAO Cai·hong，XUESheng-wei Bing-qing，WANG ofScienceand lnfommlionand (SIl呶UniversityTechnology，colle铲ofEngirl吨， Qingd∞266510，Shandong，Olina) Ah嘣：ThefractionalchromaticmⅡIll埘0fthedistaIlce graph itschromaticn眦Iberfor w啪discussed． m}一{k，七+1，七+2，k+3})and 2后≤mq2k+5 8吼屺pai埽ofill魄em，when chromatic nunlb既 words：distance tmml)er；ehnmaatic Key graph；fractional 0引言 本文仅考虑有限、简单、无向图，本节首先介绍距离图、色数以及分数色数的有关定义，然后给出有关色 数和分数色数的已有结果。 用不同的颜色给欧式平面上的所有顶点着色，使得单位距离的点着以不同的颜色所需的最小颜色数是 多少?这就是著名的平面着色问题。受这个问题启发，Eggleton¨1引入了距离图的概念： 定义1假设S是度为艿的度量空间岸的子集，D是一个正实数集，则距离图G(S，D)具有顶点集S以 及距离集D，且满足：对V菇，Y∈S，x，Y相邻当且仅当艿(鬈，Y)∈D。 这样，平面着色问题就等价于求距离图G(R2，{1})的色数，这个图的色数介于4和7之间，然而，具体的 颜色数仍然是未知的。 要考虑的是定义在整数集上的距离图，即整数距离图。给定一个有限的正整数集合D，整数距离图 I∈D的 G(Z，D)是具有顶点集z={0，±1，±2，…}、距离集D，且满足顶点髫与Y相邻的充要条件是l戈一Y 无限图，本文中所述距离图都是整数距离图。 顶点着色是图论的一个重要的研究方向，[2]中给出了有关顶点着色的一些概念： 定义2图G的一个弘顶点着色是指k种颜色对于图G的所有顶点的一个分配；如果任意两个相邻的 顶点都分配到不同的颜色，则称该着色是正常的。当图G有一个正常珏顶点着色时，称图G是肛顶点可着 色的。图G的色数是使图G为缸可着色的蠡的最小值，通常用；[(G)来表示。 收稿日期：加0r7．10-21 作者简介：刘西奎(197