最大度为6且不含4-圈和7-圈的平面图的边列表和全列表.pdfVIP

第34卷第3期 浙江师范大学学报 (自然科学版) V01．34，No．3 2011车8月 JournalofZhejiangNormalUniversity(Nat．Sci．) Aug．2011 文章编号：1001-5051(2011)03-0267-05 最大度为6且不含4．圈和7．圈的 平面图的边列表和全列表 姚潇彦 (浙江师范大学 数理与信息工程学院，浙江金华 321004) 摘 要：令G是一个最大度为△(G)的平面图．运用 Dischanging方法，进一步探究△(G)≥6的平面图的边列 表色数 ，得到了最大度为6且不含4．圈和7．圈的平面图的边列表色数为△，全列表色数为△+I． 关键词：平面图；列表染色；圈；最大度 中图分类号：0157．5 文献标识码：A Listedgeand listtotalcoloringofplna egraphs th maximum degreesixandwithout．4-cyclesand7-cycles YAO Xiaoyan fCollegeofMathematics。PhyswsandInformationEngineering，ZhejiangNormalUnwersity．Jinhua 321004．ChinaJ Abstract：ItwasstudiedthelistchromaticindexofplanegraphGwithmaximumdegree△(G)=6，itwas provedthelistchromaticindexwas厶andhtelisttotalchromaticnumberwas△+1if△【G)=6andGhadno 4-cyclesand7-cyclesbyusingthedischaringmethod． Keywords：plnaegraphs；listcoloring；cycles；mxaimum dergee 0 引 言 本文考虑的图都是简单、有限的无向图．文中未加定义的术语和记号参阅文献 [1]．用 (G)， E(G)，F(G)，△(G)和6(G)分别表示平面图G的顶点集、边集、面集、最大度和最小度 (在不引起混淆的 情况下简记为 ，E，F，△和 )． 图G的一个 一边染色是一个映射 ：E(G) {l，2，…，k}，其中k是整数．若映射 还满足对于G中 的每一对相邻边e和e，有 (e)≠ (e)，则称这个Ji}一边染色是正常的；若G有一个正常的后．边染色，则 称 G是 一边可染的；G的边色数 (G)是使得 G是 一边可染的最小的整数k；称映射 为图G的一个边 列表，如果它给每条边 eEG一个颜色集合 ￡(e)；若有一个正常的边染色 ，使得每一条边 e满足 (e)∈L(e)，则称 G是 ￡一边可染的，或称 是G的一个 边染色；若对任意表 和每条边e∈E(G)，都 收文 日期：2010-05—10；修订 日期：2010-11-23 基金项目：浙江省教育厅自然科学基金重点资助项 目 作者简介：姚潇彦(1985一)，女，浙江湖州人，硕士研究生．研究方向：运筹学；图论 268 浙江师范大学学报 (自然科学版) 2011年 有IL(e)I3k，且G是 边可染的，则称G是后一边可选的．G的边列表色数 ；(G)是使得G是后．边可选择 的最小的整数k．类似地，可定义同时染顶点和边的G的全列表色数 (G)．由定义可直接得到 ；(G)≥ (G)≥△(G)和 。(G) (G)≥△(G)+1． 下面是著名的边列表染色和全列表染色猜想： 猜想 1 如果G是一个多重图，则：1 (G)= (G)；2 (G)= (G)． 对于二部重图、奇阶完全图、多重圈、外平面图，已证明猜想l的1)成立．文献 [2]证明了对于△≥12 可嵌入非负特征曲面上的图，猜想 1成立；文献 [3]证明了对于最大度至少为7且不含4一圈的平面图及 最大度至少为6且不含4