所有的仙人掌图为1类图.pdf

第3 0 卷第1 期 2 0 0 1 年1 月 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y V 0 1 ．3 0 N o ．1 J a n ．2 0 0 1 文章纳号1 0 0 0 - 1 9 6 4 2 0 0 1 0 1 0 1 0 70 4 所有的仙人掌图为1 类图 许正权，薛秀谦 中国矿业大学理学院，江苏徐州2 2 1 0 0 8 摘要根据仙人掌图的各种结构，证明了所有的仙人掌图对全染色猜想是成立的，并进一步证明 了所有z 1 G ／3 的仙人掌图是l 类的． 关键词仙人掌图；全染色猜想；1 类图 中围分类号O1 5 7 ．5文献标识码A 图的全染色是继图的顶点染色、边染色以及组 合地图的面染色之后，人们又提出的一个新的概 念．一个图G 一 y ，E 的一个b 全染色是从yU E 到I t 一{ 1 ，2 ，⋯，h 上的一个映射仇如果对VU E 中任意两个相邻或相关联的元素m e ，都有 “q ≠州P z 时，则称P 为G 的一个正常全染色．图G 的全色数 记为斯 G ，定义为⋯ 斯 G 一m i n { k l 存在G 的一个正常 一全染色 ． 1 9 6 5 年，B e h z a d 在其博士论文中提出了一个 猜想，后来人们称之为全染色猜想，显然△ G l ≤斯 G 全染色猜想o ] 对任意的简单图G ，有 h G ≤△ G 2 ， 式中z I G 为图G 的最大度，如果X T G 一△ G 1 ，则称图G 是1 类的；如果斯 G 一△ G 2 ， 则称图G 是2 类的． 围绕着这个猜想，人们开展了对图的全染色问 题研究，其工作大致可分为3 个方面一是证明全 染色猜想对某些图成立；二是证明一般图类在一定 限制下猜想成立；这两个方面的进展不断增强着全 染色猜想的可信度．第三个方面是把界放宽，进行 估计，试图来逼近猜想中的界． 本文证明了对仙人掌图，全染色猜想是成立 的，并进而证明所有的仙人掌图是1 类的． 为了证明下面的定理，先给出一些必要定义． 相交圈如果有一个顶点属于两个圈，则称这 两个圈是相交的． 所谓仙人掌图，就是该图为连通的，其每一个 块或是圈，或是边，并把仙人掌图记为G r ．本文所 证明的仙人掌图至少含有一个圈，且△ G ≥3 ． e 表示一条边，”表示一个顶点．c 。表示与边e 相关联的顶点的颜色集合．c 0 表示与边e 相邻的 边颜色的集合． 巴表示与顶点”相关联的边的颜色集合⋯C 表示与顶点v 相邻的顶点的颜色集合． 珥表示与边e 相关联的顶点上出现的颜色集 合及与e 相邻的边上出现的颜色集合的并，即疋一 { f lc ∈G 。t ．J C 。 ． z 。表示与顶点v 相关联的边上出现的颜色及 与”相邻的顶点上出现的颜色集合的并，即“一 忙l f ∈C 。U “} ． e 表示边e 所着的颜色，G 表示顶点”所着 的颜色． 1 预备定理 引理1K 见图1 为2 类的． v _ t 』L 叫飞 图1 两个顶点的完全图 F i g ．1 T h ec o m p l e t eg r a p hw i t h2v e r t i c e s 证明显然K 2 是2 类的，由于A 一1 ，轨和口z 必须着不同的颜色，假设”。和啦分别着以颜色1 和 2 ，又e 与”。和”相关联，故e 必须着以一种与”，和 。。不同的颜色，设为颜色3 则得到 斯 K 2 A K 2 2 3 ． 所以噩为2 类的． 收藕日期，2 0 0 0 0 7 0 6 作t ■介，许正权 1 9 7 6 一 ，男，安t 省六安市人，中国矿业大学理学院硬士研究生，从事组舍与量优化方面的研究． 万方数据 中国矿业大学学报 第3 0 卷 引理2 足。 见图2 为1 类的． 证明当仉与边e 。着以1 颜色m 与边e 。着以 2 颜色煳与边岛着以3 颜色时，我们用3 种颜色就 可完成K s 的全着色，所以托为1 类的． 证毕． △ 图2 三个顶点的完全图 F i g ．2 T h ec o m p l e t eg r a p hw i t h3v e r t i c e s 引理3 长度大于1 的路是1 类的，即 h 、 尸 △ P 十1 3 ． 证明首先假设这条路有3 n 条边，3 n 1 个顶 点．并令P 口俺口2 e 2o ≈详3 。口”1 ． 对于顶点{ ”。，仉肋，⋯，v 。Ⅷ 。将其着以r ，色。 0 ，1 ，2 ，3 ，⋯．no 对于顶点{ F ，％，砘 ．．m “ 。将其着以c 。色， k 0 ，1 ，2 ，3 ，⋯，”一1 ‘ 对于顶点{ 。。佛舳，⋯，”。。 ，将其着以C 。色。 々 0 ，1 ，2 ，3 ，⋯，n 一1 ． 这样就完成了对该条路的顶点的正常着色，现 在对该条路的边进行着色． ‘1 口一“ 一0 ，1 ，2 ，3 ⋯，n 一1 ； c c 2 一‘1 女一0 1 ，2 ，3 ，⋯，n 一1 c t ⋯。一。2 20 ’1 ，2 ，3 ，⋯，n ～1 ， 从上面的证明可以知道，对于长度不为3 n 的 路，可以从长度为3 ”的路中截取一段，即为它的正 常着色． 证毕． 引理4 0 1 圈长为3 的正整数倍数的圈为1 类 的． 2 主要定理 定理1 对于所有的圈c 有 斯 C ≤△ C 2 4 ． 证明根据引理2 及引理4 ，并将圈C 分为奇 圈和偶圈． 1 若c 为偶圈，即C v i e 】口2 P 2 ⋯口2 。e 2 。口1 ．首先 给定4 种颜色m f 2 mc 4 ． 令{ v l ，‰m ，⋯，“ 抽一1 } 着以c l 色，令{ m ，仉， ”Ⅶ。 着以屯色，这样就完成了对偶圈C 的正常 的顶点着色．下面对偶圈C 的边进行着色，首先从 边旬开始． 对于小由于与e ，相邻的边还没有着色，而与 - 相关联的两个顶点为口。和钆，且气一m c 。．一屯； 所以t ， { f 。，c 2 } ，故c 。一o 或“ ．不失一般性． 令c 。一c 。．对于‰由于与e 相关联的两个顶点为 F z 和玑，且f 。。一屯 ，一f 。．又与e 2 相邻的边中，只 有e 1 已经着色，且‘．一f 3 所以以。一{ c l ，c 2 ，c 3 ，故 以，一f 。．同样，对于∞由于e 。与玑和玑关联，且岛， q ，“．一∞又与e 。相邻的边中只有岛已经着色， 且c ～一q ，所以k 一{ m c 2 ，c 4 } ，故c “ 同理可得‘。一“，。。一C 3 ，⋯。 白．对于 边e a ．由于与％相关联的顶点为Ⅵ和‰，由事先 设定的颜色可知，且岛．一m 矗，． ∞又与e 。．相邻 的边m P 2 。都已经着色，且‘，一∞‘。，一f 3 ．所 以q ，一{ c 1 ，c 2 ，c 3 ，故。‰一“． 所以对于偶圈有Z T C ≤△ c 十2 4 ． 2 若c 为奇圈，即C v i e l “ 2 e 2 - ．“ 2 n l e z ． l 矶． 同1 的证明类似，可以得到Z r C ≤△ c 2 4 ． 证毕． 定理2 对于所有△≥3 的仙人掌G t 有 斯 G T △ G r 1 ． 证明这里只对△ 3 的仙人掌图进行证明， 当然对于△ 3 的仙人掌图，其证明更简单．因为 △越大，对于圈的顶点着色和边着色时，可以使用 的颜色就越多． 首先从一个圈c ，进行着色，然后再对仙人掌 图的其余部分进行着色，由定理1 的证明可知，对 于任何圈有 h C ≤z S C 2 4 ． 假设圈c 。已经正常全着色，从这个圈开始对 圈C 。进行着色，假设圈C ，和圈C 。之间只有一条边 连接 如果圈c 。和圈c 。之间有一个交点或是一条 路，由引理1 和引理3 即得 ，即圈c 。和圈c z 之间只 有两个相邻的顶点． 令连接圈C 。和圈C 。之间的那条边为岛，岛的 两个相关联的顶点分别为轧和_ 。，即“ ， 岛，且 ％∈C ，，n ∈C 2 ．显然d 。 G ’ 一3 ，则在岛上已经 出现的颜色有3 种 由于岛还没有着色 ，令屯一 n - 为了方便起见，又不失一般性，假定这3 种颜 色为c 1 ．c 3 ’钆 即K 一{ c 1 ，c 3 ，“ ，所以吒 白． 对于C 。中的q ，由于与仉相邻的顶点中只有 万方数据 第1 期许正权等所有的仙人掌图为1 类图 c 。中顶点玑已经着色，且％ 吣其余与T J ，相邻的 顶点还没有着色．与w 。相关联的边中只有巳已经 着色，所以有“．一{ c 。．c 。} ． 若c 2 为偶圈，则令c 2 仇旬现e 2 ．oo 口2 。P z 。口l ，那么 与。。相邻的两个顶点分别为T J 。和％；若c 。为奇 圈，则令G t ／l e l u 他⋯％ 1 e 2 ． l “ 1 ，那么与u 1 相邻 的两个顶点分别为”z 和”。 。 为了能够用尽可能少的色数，令C 。中的与q 相邻的两个顶点之一着以岛的颜色．这里就令气 o ． ％首先对C 。为偶圈的情形进行证明由于 “、一h ，屯} ，所以”，可以着以c 。或“，不失一般 性，可以令 c 。l 一如’c 。2 一屯，c ”3 一c 3 ’⋯’‘、H l c 3 。 对于％，由于与％相邻的顶点为口。，％一。，且 “．一“一．一∞而与％相关联的边都没有着色，所 以巩，． ‰ ，故r 。．一c 。 或c - f ‘ ．这样就完成了 对c 。的正常的顶点着色．下面对其边进行着色，并 从e ，开始着色． 对于e 。，由于与e 。相关联的两个顶点为v 。和 口2 ，且L ，一％c b 一％与q 相邻的边只有％且t ；c 2 ，所以以， { c 1 ，c 。 ，故c 。 f 1 或“ ．对于F 2 ， 由于与e 2 相关联的两个顶点为砘和v 。，且c 。一∞ 屯一％又与e 。相邻的边中，只有白已经着色，且c 。 c 1 ，所以F 。。 c l ，％c 。} ，故c 。，一c 。．同样可得丌￡， { f 2 ，如，“ ，0 3 一C 1 ，⋯，c ，”l C 1 对于边e 。。，由于与％相关联的顶点为”，和 “ ”且c q 白，“，．一屯，又与P 抽相邻的边为巳，P 1 ， e 2 H ，且‘‘一c 2 ，c 。l c 1 ，。屯。1 一c 1 ，所以t “ 一慨， ∞岛} ，故c ‰一。 这样就证明了当C 。为偶圈时有h G t △ G T 1 ． 现在对C 。为奇圈的情形来证明． 由于“．一{ m 龟} ，所以u 1 可以着以如或“， 不失一般性，可以令 f ， 臼，c 、一屯 “3 一如，⋯’“h 吨- 对于口抽_ l ，由于与口扣十l 相邻的顶点为“ 1 2 l ，v 抽． 1 ／L c o ．一f 3 ’C v 。一屯，而与”。 。相关联的边都没有着．z 色，故f ≈。一c - 或q - 这样就完成了对G 的正常 的顶点着色．下面对其边进行着色，并从旬开始着 色． 对于e ，，由于与e ．相关联的两个顶点为功和 “ 2 ，且c ，，一“，岛．一c 。；与白相邻的边只有巳已经着 色．且t c 2 ．所以t ． { m f 3 ，故c f l 或“ ． 对于∞由于与e 。相关联的两个顶点为砘和m ，且 屯 f 2 “。一“，又与包相邻的边中，只有e 1 已经着 色．且G ，一f I ，所以砬，一{ c 1 ，c 2 。“ ，故o ，一c 4 ．同 样可得飞一{ f 2 ，C 3 * “ ，n 。一q ，⋯以∞、一c 1 ． 对于边‰，由于与％相关联的顶点为％和 ‰“，且矗． ％c ％ 。一f l ；与％相邻的边中只有 e 一已经着色，且％。 m 所以％。 k ，c z } ，故 c 。一c 。 或“ ．但是对于％十1 ，由于与％十1 相关联 的顶点为“ 0 1 和％ 1 ，且f 。I 岛。、。 l c 1 ；又与 e 2 n 十1 相邻的边为P l ，e a 而。且‘1 m ‘‘ ％‘‰ 如 或C 4 ． 若c 。一“，则以。一I t l C 2 ，“一} ，这样用4 种颜色就不可完成对仙人掌图的正常全着色． 故‘‰一f 3 ‘‰ l 一“ 这样就证明了当c 。为奇圈时有h G r △ G T 1 ． 所以△≥3 的仙人掌图是l 类图． 证毕． 3 结论 到目前为止，一般图的全色数还无法确定，只 是在某些限制下进行了一些探讨．例如对最大度做 一定限制．在早期的图的全染色研究中，人们只是 证明了图的全染色猜想对某些特殊图类是成立的， 这些特殊图类是[ “；完全图、树、完全三部图K ⋯ ， 和二分图等．在本文中证明了对于仙人掌图，其对 全染色猜想是成立的．并且进一步证明了所有△ ≥3 的仙人掌图是一类图．这为对更一般图的全 染色问题研究奠定了一定的基础． 参考文献 [ 1 ] B o n d yJA ．M u r t yUSR ．G r a p ht h o e r yw i t ha p p l l e a t i o n s r M ] ．T h eM a e h i l l a nP r e s s 。1 9 7 6 ． [ 2 ] 张忠辅，王建方．关于图的全染色一个综述口] ． 数学进展，1 9 9 2 ，2 1 4 3 9 0 3 9 7 ． [ 3 ] C h e wKt t ．Y a pHP ．T o t a lc h r o m a t i cn l l m h e ro f c o m p l e t er p a r t i t eC r a p h s [ J ] ．J o u r n a lo fG r a p hT h e o - r y ，1 9 9 2 ，1 6 6 6 2 96 3 4 ． [ 4 ] H i n dHR ．A nu p p e rb o u n df o rt h et o t a lc h m m a t i c n u m b e ro fd e n s eg r a p h s [ J ] ．J o u r n a lo fG r a p ht h e o r y ． 1 9 9 2 ，1 6 7 1 9 72 0 2 ． 万方数据 1 l O 中国矿业大学学报 第3 0 卷 O nA l lC a c t u sG r a p h sB e i n gT y p eO n e X UZ h e n g q u a n ，X U EX i u q i a n C o l l e g eo fS c i e n c e ，C U M T ．X u z h o u 。J h n g s u2 2 1 0 0 8 ，C h i n a A b s t r a c t T h a ta l lc a c t u sg r a p h sa r et u r cf o rt h ec o m p l e t ed y e i n gc o n j e c t u r ew a sp r o v e da c c o r d i n gt ov a r i o u s s t r u c t u r e so fc a c t u s ．T h er e s u l ts h o w st h a ta l lc a c t u sg r a p h sw i t h △≥3a r et y p eo n e ． K e yw o r d s c a c t u sg r a p h s ；t h et o t a l c o l o r i n gc o n j e c t u r e ；t y p eo n eg r p h s 中国矿业大学学报 2 0 0 1 年第3 0 卷第2 期要目预告 题目 第一作者 高瓦斯煤层开采的新思路及待研究的主要问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯周世宁 G F 增强尼龙1 0 1 0 复合材料的摩擦学性能研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯葛世荣 超高压直残剪试验系统及其初步应用⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯周国庆 任丘雾迷山组储层、水、结垢中微量元素赋存特征⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯冯启言 煤层气项目经济评价方法及应用研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯杨永国 卸压法治理井壁结构破碎的模拟试验研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯吕恒林 大空间、复杂结构建筑物平移技术研究与应用⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯袁广林 煤矸石的破碎压密作用机制研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯姜振泉 复合材料层台地基大厚板的静动力分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯高荣誉 用口分布函数模拟颗粒在跳汰床层中的分布⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯樊民强 基于公共知识库和小变换的混合图像编码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯于洪珍 有限变形激光频谱图像的计算机自动分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯刘艳华 哈密、淮北煤变质程度与稀土元素的关系研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯赵志根 基于供应链的现代生产集成系统体系研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯钱旭 城镇地价内涵及“1 1 ”模式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯刘金平 含亚甲基芳烃的脱氢研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯陆瑾 煤表面二次离子质谱分析的无机定性分析方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯粱汉东 桩基工程投标决策方法研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯曹丽文 煤矿环形综合业务网中“1 ／2 路径和”路由算法的研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯张申 跨采软岩巷道锚注加固技术的实验研究⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯马史顶 万方数据