一类特殊图的邻点可区别全染色

格式：pdf
大小：157.64 KB
文档页数：2

下载文档原格式

T-型六角系统的邻点可区别I-全色数

2020年10月第40卷第5期天水师范学院学报Journal of Tianshui Normal UniversityOct.，2020V〇1.40 No.5r-型六角系统的邻点可区别/-全色数杨随义(天水师范学院数学与统计学院，甘肃天水741001)摘要：图G的邻点可区别/-全染色是一个满足相邻顶点色集合不同的/-全染色，其中任意一点的色集合为该顶点及其关联边所染颜色构成的集合.将其所需颜色的最小数称为邻点可区别/-全色数，记为;^(G).运用数学归纳法研究了 r-型六角系统厂>多0)的邻点可区别/-全染色，并证明了当n多0时，；^(7\)=3;当n这1时，獻)=4.关键词：r-型六角系统；邻点可区别/-全染色；邻点可区别/-全色数中图分类号：0157.5 文献标识码：A1预备知识图染色作为图论研究的重要方向之一，被广泛应用于信息计算科学、通信网络、交通运输等领域，为实际问题的解决提供了重要的理论依据和最优策略.图染色最早起源于四色问题的研究，随后一系列经典染色如点染色、边染色以及全染色等相继被提出.m点染色是若干种颜色在顶点(边）上的一个分配，且相邻顶点（边）分配不同的颜色，将所用的最少颜色数称为点（边）色数.图的全染色是若干种颜色同时在顶点和边上的一个分配，且满足相邻顶点与相邻边以及关联元素分配不同的颜色，类似地，将所用的最少颜色数称为全色数.1941年，Brooks证明任意一个既不是奇圈也不是完全图的连通图，其点色数不超过A.1964 年前后，Vizing和Gupta分别独立证明了任意一个图的边色数不超过A+1.此外，Vizing还猜测：任意一个图的全色数不超过A+ 2,即后来众所周知的全染色猜想（T C C).染色问题已被证明是一个N P-难问题，因此，为了进一步探索T C C猜想，国内外学者随后又相继提出了一系列可区别染色.2005年，张忠辅等"]提出了图的邻点可区别全染色的概念，并给出了圈、完全图、完全二部图等一些特殊图类的邻点可区别全色数，并猜测图的邻点可区别全色数A+ 2.此后，国内外学者针对这一猜想展开了研究.[2_31为了推动邻点可区文章编号：1671-1351 (2020) 05-0019-03别全色数猜想的研究，张忠辅等[41在邻点可区别全染色的基础上，提出了邻点可区别/-全染色的概念.随后王继顺M研究了蛛网图、渔网图以及联图及的邻点可区别/-全染色.张婷、赵慧霞等171给出了图（75乂见…的邻点可区别/- 全色数•六角系统作为化学图论中重要的研究对象，受到了国内外学者的广泛关注.六角系统图是由正六边形所组成的平面图网络，其构型多种多样，不同的构型其化学性质也各不相同.r-型六角系统是一类特殊的六角系统，它是由一个正六边形中心分别向3个间隔方向延伸n个正六边形直链所构成的对称图，简称》阶r-型六角系统链.最近，王文杰等181首先研究了 r-型六角系统链的点可区别边染色.本文以此为动机，研究了:r-型六角系统的邻点可区别/-全色数，并得到了其邻点可区别 /-全色数.定义1.1[”设6是阶至少为2的连通图，&是正整数，/是V(G)U£(C)到{1，2，"•，叼的映射，对任意ueK(G)，记C(u) = {/(“)}“託.如果(1)对于任意肌，有f(uv)¥^f{vw);⑵对于任意有/(u)^f(v),f{u)t^/M ;则称/为C的正常全染色，进一步，如果 /还满足收稿日期：2020-09-17作者简介：杨随义（1977-),男，甘肃天水人，天水师范学院数学与统计学院副教授，硕士。

图的染色ppt课件

9
❖ 定理6.4 二分图属于第一类图，即χ’(G )=Δ(G)
❖ 证 G为二分图，假定χ’(G )=Δ(G) +1，设α是一个最优边染色，必有顶点u适合Cα(u) ＜ dG(u) 。u 显然满足引理6.2的条件，所以G包含一个长度为奇数的回路。因而不是二分图，导出矛盾。故
χ’(G )=Δ(G) +1，χ’(G )=Δ(G)
χ(G )·α(G) ≥p
❖ 证明设S是G的一个最大点独立集，|S|=α(G) ，令 S中的点染第1色，V(G)中其余p-α(G) 个点分别染
第2,3,…,p-α(G) +1色，这样得到G的一个正常p-
α(G) +1点染色，于是χ(G ) +α(G) ≤p+1
❖ 设χ(G ) =k，则V(G)可以划分成k个色组
显然这些边构成k2n的一个完美匹配f对每一个完美匹配着以不同的颜色按定义这种着色是正常的故k2n2n1又k2n2n2n1所以2n2n1把上图中的中心点及关联边去掉则我们得到一个图且从原来在中的正常的2n1边着色得到中的一个正常的2n1边着色
图的染色
四川师范大学数学与软件科学学院
周思波
精选ppt
1
边染色
到颜色集S={1,2,…,k}建立了一个映射β, Vi =β-1(i)。如果在某个k点染色β中，任何两个同色点都不相邻，
即每个Vi都是点独立集，那么这个β就称为正常k-点染色。若图G有正常k点染色，则称G为k点可染的，
简称为k可染色。
精选ppt
16
例子
v1 e1
v4
e2
e8 e7 v6 e9 e10
❖ 定理6.8 若G是k色的临界图，则k≤δ(G)+1

有关图的染色问题的研究

j 2 1
nj j 1
.
引理 3[2 ] 设 G 为阶为 v ,边数为 e 的Δ2 临界图. (1) 若 3 ,则 e (5v 1) / 4 ; (2) 若Δ = 4 ,则 e 5v / 3 ; (3) 若 5 ,则 e 2v 1 ; (4) 若 6 ,则 e (9v 1) / 4 ;
同的颜色，所以对任意图 G 的边色数有 ' G ，其中指图 G 的最大度。 1964 年，苏联数学家 V.G.Vizing 给出了关于图边染色的一个突破性结论，他指出了简单图 G 的边色数与度之间的关系。 Vizing 定理：任意(简单，无向) 图 G 的边着色数 (edge chromatic number)
在将近半个世纪的漫长岁月里，人们一直在为解决简单图的分类问题做着不懈的努力。解决一般图的分类问题相当困难，因此人们关心平面图等特殊图的分类问题。对于简单平面图，1965 年，Vizing 自己证明了，如果 8 则是第一类的。而对于 2,3, 4,5 的情况则同时有第一类和第二类的图存在。比如，把正多面体的其中一边截成两条，即可得到 3, 4,5 的平面图，都有 G C 2 ；而任何长度是奇数的圈 ( 比如三角形 ) 就是 2 的第二类图。并对剩余的两种情况， Vizing 也提出了猜想。平面图 Vizing 猜想：任何简单平面图如果 6 7, e(G) v (G) ，则是第一类的。对于 7 的情况，在 2001 年 Sanders & Zhao 给出了肯定的结果：G C1 。而对于 6 的情况，至今尚未解决。 2.3 一些结论首先介绍几个常用的引理. 引理 1 (Vizing 邻接引理) 设 G 为临界图,且 uv E (G), d (v) k , 则有 (1) 若 k , u 至少相邻于 G 的 k 1 个度数为的顶点; (2) 若 k , u 至少相邻于 G 的两个度数为的顶点. 引理 2[2 ] 若 G 为临界图( ≥3) ,则 n 2

细胞分裂图解

细胞分裂识图考点分析1、细胞的生长和增殖的周期性。

Ⅰ2、细胞的有丝分裂。

Ⅱ3、细胞的减数分裂。

Ⅱ【拓展提升】1、基因与染色体的关系。

Ⅱ2、基因的分离规律和自由组合规律。

Ⅱ【与识图相关的知识要点】1、减数分裂与有丝分裂的比较表（课前完成）比较项目减数分裂有丝分裂细胞分裂次数染色体复制次数联会、四分体是否出现有无同源染色体着丝点分裂、染色单体分开的时期子细胞染色体数目子细胞名称和数量2、（同种生物）两种分裂方式中染色体与DNA变化对照表（课前完成）项目有丝分裂减数分裂间期前期中期后期末期性原细胞初级性母细胞次级性母细胞性细胞染色体数目变化2NDNA含量变化2a3、有丝分裂与减数分裂细胞分裂图的鉴别（以二倍体生物细胞为例）：（1）几个特殊分裂时期的比较分析①细胞分裂前期：（如图）②细胞分裂中期：（如图）③细胞分裂后期：（如图）③有丝分裂、减数分裂图形辨析（以二倍体为例）4、其他与减数分裂和有丝分裂有关的图形题分析4.1坐标曲线图坐标曲线图一般用于考查细胞分裂过程中染色体及DNA含量关系的判断及分裂时期的判断。

例1、下列图示中，横轴表示细胞周期，纵轴表示一个细胞核中DNA含量或染色体数目的变化，请分析图示，表示有丝分裂DNA含量变化、染色体数目的变化和减数分裂DNA含量变化、染色体数目的变化的依次是（）4.2柱形图柱形图常用于考查细胞分裂各时期的染色体、染色单体及DNA等的数量关系特点。

熟悉细胞分裂各时期中染色体、染色单体及DNA的变化特点是解答此类问题的关键。

例2．下图A、B、C、D分别表示某哺乳动物细胞（2n）进行减数分裂的不同时期，其中a表示细胞数目。

请判断b、c、d依次代表（）A．DNA分子数、染色体数、染色单体数B．染色体数、DNA分子数、染色单体数C．DNA分子数、染色单体数、染色体数D．染色单体数、染色体数、DNA分子4.3扇形图扇形图常用于考查细胞分裂各时期的判断。

例3.下图表示细胞有丝分裂一个细胞周期所用的时间，下列说法正确的是（）①甲→乙过程中着丝点会分裂②乙→甲的过程有蛋白质合成③一个细胞周期是指甲→甲的全过程④一个细胞周期是指乙→乙的全过程A、①②③B、①②④C、③D、④4.4细胞分裂模式图和坐标曲线图相结合细胞分裂模式图常用于考查细胞分裂各时期染色体变化的特点，如根据图中细胞的特点判断细胞属于有丝分裂还是减数分裂的哪个时期、判断细胞的雌雄性等。

关于几类图的邻点可区别关联色数

Ｖｏ．２Ｎｏ５１２．
Ｓｅｐ．２０８０
文章编号：６２６９（Ｏ８０ — １５０１７～１７２Ｏ）５００ — ３
关于几类图的邻点可区别关联色数
王文丽，刘西奎，周薇
（山东科技大学信息科学与工程学院，山东青岛，６５０２６１）
ａｅｄｆｅｅｔｅｍｏｔｙｓｕｙｔｅａｊｃｎｅｔｘｄｓｉｇｓｉｇｉｃｄｎｅｃｌｒｎｕｅｆｒｉｒｎ．Ｗｓｌｔｄｈｄｅｔｖｒｅ－ｉｔｕｈｎｎｉｅｃｏｏｉｇｎｍｂｒｏｆａｎ
一
｛，）Ｉ（Ｐ口∈ Ｖ，ｅ∈ Ｅ，与ｅ相关联｝Ｇ的关是
１基础知识
图的染色问题是图论研究的经典领域．网络在问题．组合分析和实际生活中有着广泛的应用，图是论的主要研究内容之一．文研究了图的邻点可区别关联着色，一步刻画了风车图、进齿轮图的邻点可区别关联着色，此基础上研究扩充的图Ｄ… 的邻点在可区别关联色数。文中，本我们用（，Ｇ）分别Ｇ）Ｅ（表示图Ｇ的点集和边集，Ｇ）表示Ｇ的最大度， △（
中图分类号：Ｏ１７５５．文献标识码：Ａ
Ｔｅａｊｃｎｅｔｘｄｓｉｇｉｉｇｉｃｄｎｅｈｄｅｔｒｅ’ｉｔｕｓｎｉｅｃａｖｎｈｎ
ｃｌｒｎｇｎｕｂｒｏｌｓｅｒｐｓｏｏｉｍｅｆｃａｓｓｇａｈ

地球物理勘查图图式图例及用色标准

符合此类规定格式的图件有： #$ "% &’’’’ ( " % "’’’’’’ 物探工作，其面积达 ) 幅以上同比例尺地形图面积时，其主要成果图件（平面图、剖面平面图等）采用国际分幅； *$ " % "’’’’ ( " % !&’’’ 物探工作，其效果显著，近期仍有向外扩展的可能，或属于基础性工作（面积达 ) 幅以上相同比例尺地形图面积）的主要成果图件，采用国际分幅，其他情况下采用方里分幅或自由分幅。 · !),+ ·
6 编制总则
% " # 编制的基本要求 07 图外要素：规范、完整、匀称、美观； 87 注记：准确、合理、紧凑、清晰、协调； )7 图例：齐全、简明、实用； &7 色标：简便、醒目、适宜、和谐。
% " $ 表示方法总则 % " $ " # 本标准涉及的有关地质矿产、测绘等方面的内容与规格应参照国家相应的标准（或规范）的规定。 % " $ " $ 各类物探平面图以标准分幅图为基础，加以整饰，完善。
指位置坐标轴在垂直方向，参数坐标轴在水平方向。 · #%&& ·
主要包括：测井和井中物探剖面图。除图名、比例尺、密级、责任表同国际分幅格式相同并保持原位外，其他图内、外要素基本布局如下图示： !" 测井物探剖面：
图# $" 井中物探剖面：
图% · )(’& ·
图中，根据实际需要，! 可作 " 的底图，合并绘制；柱状图中可包括岩心采取率、品位分析等结果；
* 引用标准
+, ’ - ./ 区域地质图图例（) 0 .%%%%） +, 1234 5 (%* ) 0 *. 万地形图编绘规范及格式 +, .6’) ) 0 .%%% ) 0 )%%%% 地形图图式

路和圈的笛卡尔积的邻点强可区别全染色

ｆ
证明：当３时图中有相邻的４度顶点，由引理知（Ｐ３ＸＣ３） ≥６。为证明（尸３ × Ｃ３）＝６，只需给出Ｐ３ＸＣ３的一种６一邻点强可区别
科技信息
路和圈晌笛卡尔积硇邻点强可区别星染色
兰州交通大学数理学院陈小强张园萍
［摘
王枭翔
要］本文介绍了部分特殊图类的笛卡尔积图的邻点可区别全染色的有关重要结论，并在此基础上讨论阶路和ｎ阶圈的笛卡尔
积ＰｘＣ的邻点强可区别全染色，得到了＂阶路和阶圈的笛卡尔积ＰｘＣ的邻点强可区别全然色数（ＰＸＣｎ）＝６。
定理３圈和圈的笛卡尔积ＣＸＣ的邻点可区别全染色数
。，
＿厂ｌ１）＝５；ｆ（叫ｌ２）＝２；ｆ（ｗｚＯ＝３；ｆ（ｗ２ｚ）＝１；ｆ（ＷｌｌＷｌ２）：３；ｆ（ｗｎｗｍ）＝４；ｆ（ｗ２１ｗｌ１）＝６；ｆ（ｗｍｗ２Ｊ＝２；
（ｃｘＰ）＝６
引理对于阶数至少为３的图Ｇ，若Ｇ中有两个最大度顶点相邻，则
集合也不同，所以有（Ｐｚ × Ｃｚ）：６。
情况２：＝３时（Ｐ３ ×Ｃ３）＝６
（Ｇ） △ （Ｇ）＋２
２．主要内容本文在已给出的一些特殊图类的笛卡尔积图的染色结果的基础上讨论分析了目前尚未报道的阶路和阶圈的笛卡尔积ＰＸＣ的邻
Ｐ × Ｃ。的一种６一邻点强可区别的全染色方法，如图２所示：

公考逻辑图推

度逻辑判断一、图推常考：1、数量规律（重点）2、空间规律（重点）3、属性规律4、特殊规律：功能元素，图形间位置关系5、位置/样式规律较少,结合有点二、定义常考：1、单定义占90%2、多定义占10%三、类比常考：1、对应关系（50%）2、比喻象征3、包容关系：包容+对应4、近义关系、语法关系四、逻辑常考：1、加强论证（40%）2、削弱论证（20%）3、日常结论（20%）4、翻译推理，真假推理，其他（整体很少）图形推理一、图推考点：（注意图形特征匹配考点）1、位置规律：元素组成相同优先考虑位置（1）、平移（就近看图形变化，）方向：A直线（上下，左右，对角线），B绕圈（顺逆时针）步数：恒定，递增（等差递增）（2）、旋转（看选项差异，排除选项）方向：顺逆时针常见角度：45，90，180（3）、翻转左右翻转：图形沿竖轴对称（不必区别向左还是向右翻，因为图形都一样）上下翻转：图形沿横轴对称对比思维，看选项差异，排除选项，如遇到九宫格题目，可以直接看第二列规律，不必把每一列规律都推出来。

2、样式规律：元素组成似，元素重复出现；线条重复出现（1）遍历——缺啥补啥（相同元素重复出现，九宫格和两组图居多）注：1、外框缺啥补啥，2、内部图案缺啥补啥3、相减和求异不严格区分（2）、加减同异：相加相减、求异（去同求异）、求同（去异求同）A、相加、相减B、求异（去同求异）C相同图形重复出现，优先考虑加减。

求异和旋转一起出现（3）、黑白运算：图形轮廓和分割区域相同，不同区域“黑白”颜色不同且黑块数量不成规律。

方法：相同位置做运算注意：黑块数量相同，优先考虑位置平移黑块位置不同，优先考虑黑白运算“坑”：黑+白与白+黑未必一样3、属性规律：元素组成不相同、不相似、优先属性（1）、对称性A：轴对称（两侧一样）考点：对称轴方向和数量特征图：（出现箭头优先考虑轴对称）B：中心对称（绕某点，旋转180度，跟原图一样，考试中卷子倒过来看，跟原图一样就是中心对称图形）特征图：N Z S有2条垂直的对称轴，则该图既是轴对称又是中心对称轴对称图形一、新特征图图形两侧一样二、新考法1、对称轴的方向和数量（运算）2、对称轴与图形的线条关系（平行或者垂直）4、两个对称轴的线条关系（平行或垂直）三、技巧：把对称轴画出来（2）、曲直性A：全曲线B：全直线C：曲+直（3）、开闭性1、全封闭例如：2、全开放例如：完整图形留了小开口，可以考虑封闭性4、数量规律（点线角面素）：元素组成不相同不相似、数量规律明显（元素组成不相同、不相似优先考虑属性，不行再数量）（1）、点：点的数量（交点）A：与线的交点，直曲相交的切点也属于交点B：直曲线的两个端点不属于交点数点特征图：Ⅰ、线条交叉明显（大树杈）Ⅱ、乱糟糟一团线交叉Ⅲ、相切较多细化考点：出现数点特征图，但整体数点无规律，考虑曲直交点（2）、线：线的数量A：直线数特征图形：多边形，单一直线（为了补充直线规律，有时候单一画个直线）B：曲线数：特征图形：曲线图形（全曲图形、圆、弧）注：单一直线或者曲线，可以看做直曲图形特征图内外框组合图形：外框直线和内框图形直线可以分开数看规律C：一笔画：线条不重复情况下，可以一笔画成，线条不能重复特征图形：一笔画：一笔画问题：A：线条之间连通。

6图染色问题

图着色问题的应用－交通管理系统图着色问题的应用－交通管理系统
接下来的通行方向为结点（如图12接下来的通行方向为结点（如图12-8所示），考虑结点分组
图着色问题的应用－交通管理系统图着色问题的应用－交通管理系统
图例中分组情况如下：绿色：AB，AC，AD，BA，DC，绿色：AB，AC，AD，BA，DC，ED 蓝色：BC，BD，蓝色：BC，BD，EA 红色：DA，红色：DA，DB 黄色：EB，黄色：EB，EC
b c a d
h g f
e
顶点色数即为最少房间数数
图着色问题的应用－交通管理系统图着色问题的应用－交通管理系统
对于一个多叉路口，设计一个交通信号灯的管理系统：对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。我们将通行方向作为结点，如果某些通行方向不能同时进行，则在相应的结点间连一条线于是问题就转化为将结点分组，使得相连结点不在同一组里。例3：如图12-7所示，某交叉路口有A，B，C，D，E,五条街道，请设计一：如图12- 所示，某交叉路口有A E,五条街道，请设计一个交通信号灯的管理系统。图12-7 12分析：首先考虑可以通行的方向
b c a d
h g f
e
解（1）各顶点按度数递减次序排列：
c，a，e，f，b，h，g，d；（2）对c和与c不邻接的e，b着第一种颜色；（3）对a和与a不邻接的g，d着第二种颜色；（4）对f和与f不邻接的h着第三种颜色。
b c a d
h g f
e
边的着色问题可以转化为顶点的着色问题。
图着色问题的应用－安排考试问题
着色问题的应用－排课时间表问题
问题描述：给出老师与班级的任课关系，以及教室数的限制，给出一个合理的排课方案。匹配、边着色或顶点着色未解决好

若干Mycielski图的邻点可区别均匀全染色

为困难，甚至是一些特殊图，至今所知结ቤተ መጻሕፍቲ ባይዱ 甚少。文献［８—１１］研究了几类简单图、二部图和联图的邻
点可区别均匀全色数。
Ｍｙｃｉｅｌｓｋｉ图是一类应用较广泛的图，本文利用构造法和匹配法研究了路、圈、星和扇的Ｍｙｃｉｅｌｓｋｉ图
｛ｅＩｅ ∈ （Ｇ），（ｅ）：ｉ｝，。：。ｕＥ。，若满足：Ｖｉ， ∈｛１，２， …，ｋ｝，ｌｌＴｌｌｌ ≤１，则称厂为图Ｇ的
一
个一邻点可区别均匀全染色，记为ｋ－ＡＶＤＥＴＣ，且称（Ｇ）＝ｍｉｎ｛ｋ』Ｇ的ｋ－ＡＶＤＥＴＣ｝为图Ｇ的邻点
（１Ｉ）对Ｖｕ ∈Ｅ（Ｇ），有，（ｕ）≠ｆ（），ｆ（）≠ｆ（ “ ），ｆ（／Ｌ）≠ｆ（），则称，为图Ｇ的ｋ一正常全染
色。进一步，若厂还满足：（ｍ）Ｖ／／，Ｖ∈ Ｅ（Ｇ）， “≠ ，Ｃ（ｕ）≠ Ｃ（），则称／为图Ｇ的一个ｋ一邻点可区别全染色，记为
０引言
本文所考虑的图均为连通、有限、无向的简单图。２００４年，文献［１］提出了邻点可区别全染色的概念及相关猜想，给出了完全图、完全二部图、圈、扇、轮和树等简单图的邻点可区别全色数。文献［２—３］提出了图的均匀全染色概念及相关猜想。文献［４— ６］研究了一些简单图的均匀全色数。在此基础上，文献［７］给出了图的邻点可区别均匀全染色的概念及其几类简单图的倍图的邻点可区别均匀全色数，并提出相关猜想。由于邻点可区别均匀全染色比邻点可区别全染色更加困难，所以这个猜想就显得甚

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

ＯｎｔｅＡｄａｅｔｒｅｓｉｇｉｈｎｏａｌｒｎｆｐｃａａｈｊｃｎｔｘＤｉｎｕｓｉｇＴｔｌｏｉｇｏＳｅｉｌｈＶｅｔＣｏａＧｒｐ
ＤＵｉｎｗｅ．ＵＮａ－ｉｇＪａ — ｉＳＸｉｏｌｎ
（ｈｏｏｃｎｅＮｒｎｖｒｔｏＣｉａＴｉｕｎ００５，ｈｎｉＳｏｌｆｉｃ，ｏｔＵｉｅｓｙｆｈｎ，ａｙａ３０１Ｓａｘ）ｃＳｅｈｉ
ｔｔｌｈｏｔｕｅｆｔｅｒｇｌｒｂｐｒｔｒｐｒｂａｎｄｏａｒｍａｉｎｍｂｒｅｕａｉａｉｇａｈａｅｏｔｉｅ．ｃｃｏｈｔｅ
［ｅｏｄ］Ｒｇｌｒｉａｉｒｐ；ＡｊｃｎｅｅｉｉｇｉｉｇｔｔｏｒｇｄａｅｔｖｒｘｄｓｎｉｉｇｔｌｃｒｍａｃＫｙｗｒｓｅｕａ；Ｂｐｒｔｇａｈｄａｅｔｖｒｘｄｓｎｓｎｏｌｃｌｉ；Ａｊｃｎｅｅｉｉｇｓｎｔａｈｏｔｔｅｔｔｕｈａｏｎｔｔｕｈｏｉ
（）ｃ｛ｕｕ｛Ｉ，∈ （）Ｇ，（＝），１ＥＧ，ＥＧ｝如果：记）ｆ｝（ｌ）１３３Ｅ（）．１）对任意 “，Ｗ∈ＥＧ，＃ｗ，ｆ（ｖ＃）Ｖ（）ｕ有ｕ）ｆ＠；
２）对任意删 ∈ＥＧ，ｌｕ＃）ｕ ≠ （）有ｆ），）），
ｎｕｍｂｅｒ．
Ｏ引言
文献［中，１］张忠辅等提出了图的邻点可区别全染
正则二部图为Ｇｎｎ（，，下面讨论当ｎ（ｄ）文献『１构造的一类ｍ０ｍｏ３时，２中
正则二部图的邻点可区别全染色．以下Ｇ（｜均指ｎｉ，｝）
ｃｌｉｇｏａｃｓｆｅｕａｉａｔｅｇａｈａｄｉｗｓｐｏｅｙｕｉｅｍｔｏｆｎｌｓｔｃｒ．Ｆｅａｊｃｎｖｒｘｄｔｇｉｉｇｏｒｆｌｓｇｌｂｐｒｔｒｐｎａｒｖｄｂｓｇｔｅｄｏａｉｓｕｔｅｈｄａｅｔｅｅｉｉｕｓｎｏｎａｏｒｒｉｔｎｈｈａｙｓｒｕｔｓｎｈ
记号可参看文献『１３．１基本概念与引理
定理ｌ对于３正则二部图Ｇｎ，３（＞，：一（ｎ，ｎ３）有）Ｘ。Ｇ＝。）５（证明：二部图Ｇｎ，，）设（ｒ３的顶点集可化分为＝ｔ｛１３ …，２１ｙ｛２４，，｝如下方法构造ｖ，，Ｕｎ｝＝， … ．－，按３正则二部图：将２一先ｎ个顶点构成一个圈ｆ是一这
个２正则的二部图）然后，加边Ｖ，３ … … ，一；添１ｖｖｙ，
Ｙ２－２，ｎ５Ｕｎ一Ｖ２，Ｖ２１３ｎ一Ｖ４．
定义１［设Ｇ是阶至少为２的连通图．正１：１５ｋ是
整数是ｖＧｕＥＧ到｛， … ，的映射，（）（）１２）对任意Ｍ ∈Ｖ
一
类特殊图的邻点可区别全染色
杜建伟，晓玲孙
（北大学理学院，西中山太原００５）３０１
【摘
要】在圈的色数算法基础上，用分析结构的方法，利对一类特殊正则二部图的邻点可区别全染色问题进行了
文献【］２中构造的正则二部图．
色的概念．本文给出了文献ｆ提出的一类正则二部２忡
图的邻点可区别全色数．本文所考虑的图Ｇ都是无向
连通的简单图，采用ＶＧ、（）（）ＥＧ分别表示Ｇ的点、的边
集合，Ｇ表示Ｇ的最大度．中未加说明的术语或 △（）文
研究．到了它们的邻点可区别全色数．得
【关键词】正则；部图；点可区别全染色；点可区别全色数二邻邻
【中图分类号】０１７５【５．文献标识码】Ａ【文பைடு நூலகம்编号】１０— ７Ｘ（０８０ — ０６００３７３２０）６０５－２
第２３卷第６期ｆ第１５期）总０
机械管理开发
ＭＥＣＨＡＮＩＣＡＬＭＡＮＡＧＥＭＥＮＴＡＮＤＤＥＶＥＬＰ０ＭＥＮＴ
２００８年ｌ２月
Ｄｃ２０ｅ．０８
Ｖ１３Ｎ．ＳＭＮ．５ｏ．ｏ２６（Ｕｏ０）１
［ｓｒｃ］Ｂｓｄｏｅａｏｉｍｏｔｅｃｒｍａｃｎｍｂｒｆｙｌ，ｈｓｐｐｒａｌｄｓｕｓｄｔｅａｊｃｎｅｅｉｉｇｉｉｇｔａＡｂｔａｔａｅｎｔｌｒｈｆｈｈｏｔｕｅｃｅｔｉａｅｍｉｙｉｓｅｄａｅｔｒｘｄｓｎｕｓｎｔｈｇｔｉｏｃｎｃｈｖｔｔｈｏｌ
由引理１Ｘ（）Ｉ５因此只需证明Ｇ存在５知：。Ｇ＞，一
ＡＶＴＤＣ即可．ｃ｛，２，｝表示５种颜色的集合．设＿０ｌ，４，３，
）删）则称／为Ｇ的七正常全染色。 ≠ ，一