平面图的无圈边染色.pdf

《平面图的无圈边染色.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３２卷第３期江苏师范大学学报（自然科学版）Ｖｏｌ．３２，Ｎｏ．３２０１４年９月ＪｏｕｒｎａｌｏｆＪｉａｎｇｓｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｓｅｐ．，２０１４文章编号：２０９５４２９８（２０１４）０３００２２０５平面图的无圈边染色王艺桥１，舒巧君２（１．北京中医药大学管理学院，北京１０００２９；２．杭州电子科技大学理学院，浙江杭州３１００１８）摘要：一个图犌的无圈边染色是一个正常的边染色，使得不产生双色圈．Ｆｉａｍˇｃｉｋ和Ａｌｏｎ等分别提出了著名的无圈边色数猜想：每一个简单图犌是无圈边（Δ

2、＋２）可染的，其中Δ是犌的最大度．证明了对于不含３圈和５圈相邻的平面图猜想成立．关键词：无圈边色数；平面图；最大度；圈中图分类号：Ｏ１５７．５文献标识码：Ａ犱狅犻：１０．３９６９／ｊ．ｉｓｓｎ．２０９５４２９８．２０１４．０３．００６犃犮狔犮犾犻犮犲犱犵犲犮狅犾狅狉犻狀犵狅犳狆犾犪狀犪狉犵狉犪狆犺狊１，ＳｈｕＱｉａｏｊｕｎ２ＷａｎｇＹｉｑｉａｏ（１．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，ＢｅｉｊｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎｅｓｅＭｅｄｉｃｉｎｅ，Ｂｅｉｊｉｎｇ１０００２９，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，Ｈａｎｇｚｈｏ

3、ｕＤｉａｎｚｈｉＵｎｉｖｅｒｓｉｔｙ，Ｈａｎｇｚｈｏｕ３１００１８，Ｚｈｅｊｉａｎｇ，Ｃｈｉｎａ）犃犫狊狋狉犪犮狋：Ａｎａｃｙｃｌｉｃｅｄｇｅｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈ犌ｉｓａｐｒｏｐｅｒｅｄｇｅｃｏｌｏｒｉｎｇｓｕｃｈｔｈａｔｎｏｂｉｃｈｒｏｍａｔｉｃｃｙｃｌｅｓａｒｅｐｒｏｄｕｃｅｄ．Ｔｈｅａｃｙｃｌｉｃｃｈｒｏｍａｔｉｃｉｎｄｅｘ犪′（犌）ｏｆ犌ｉｓｔｈｅｓｍａｌｌｅｓｔ犽ｓｕｃｈｔｈａｔ犌ｈａｓａｎａｃｙｃｌｉｃｅｄｇｅｃｏｌｏｒｉｎｇｕｓｉｎｇ犽ｃｏｌｏｒｓ．ＦｉａｍˇｃｉｋａｎｄＡｌｏｎｅｔａｌ，ｉｎｄｅｐｅｎｄｅｎｔｌｙ，

4、ｍａｄｅａｃｏｎｊｅｃｔｕｒｅｔｈａｔｅｖｅｒｙｓｉｍｐｌｅｇｒａｐｈ犌ｈａｓ犪′（犌）≤Δ＋２，ｗｈｅｒｅΔｄｅｎｏｔｅｓｔｈｅｍａｘｉｍｕｍｄｅｇｒｅｅｏｆ犌．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｉｓｃｏｎｊｅｃｔｕｒｅｆｏｒｐｌａｎａｒｇｒａｐｈｓ犌ｗｉｔｈｏｕｔａ３ｃｙｃｌｅａｄｊａｃｅｎｔｔｏａ５ｃｙｃｌｅａｒｅｃｏｎｆｉｒｍｅｄ．犓犲狔狑狅狉犱狊：ａｃｙｃｌｉｃｅｄｇｅｃｏｌｏｒｉｎｇ；ｐｌａｎａｒｇｒａｐｈ；ｍａｘｉｍｕｍｄｅｇｒｅｅ；ｃｙｃｌｅ何图犌，有犪′（犌）≤６４Δ．当前最好的上界犪′（犌）≤０引言［４］４Δ－４，由Ｅｓｐｅｒｅ

5、ｔ等得到．一些特殊图的无圈边［５］本文考虑有限简单图．给定一个图犌，用犞（犌）染色已被广泛研究，如最大度为３的图，为４的［６－７］［８］和犈（犌）分别表示它的顶点集和边集．令犆犽＝图．对于平面图犌，Ｂａｓａｖａｒａｊｕ等证明了［９］狌１狌２…狌犽狌１是犌中长为犽的圈．若两个圈至少有一犪′（犌）≤Δ＋１２．Ｗａｎｇ等将１２降到７，且证明了当条公共边，就称这两个圈为相邻的．设Δ和δ分别表犌符合以下几个条件之一时，猜想１成立：ｉ）不含３［１０］［１１］［１２］示一个图犌的最大度和最小度．圈；ｉｉ）不含４圈；ｉｉｉ）不含５圈；ｉｖ）不含３［１３］图犌的正

6、常边犽染色是指映射犮：犈（犌）→圈和４圈相邻．相关结果参见［１４］．｛１，２，…，犽｝，使得相邻的边染不同的颜色．犌的边色本文旨在研究不含３圈和５圈相邻的平面图的数（犌）是指使得犌是边犽可染的最小整数犽．无无圈边色数．将证明此类图也是满足猜想１的，这在χ′圈边犽染色是指犌的一个正常的边犽染色，使得不一定程度上改进了文献［１１－１２］中的结果和扩充了产生双色圈．无圈边色数犪′（犌）是指使得犌是无圈［１３］中的结果．边犽染色的最小整数犽．由著名的Ｖｉｚｉｎｇｓ定理知，１结构分析Δ≤χ′（犌）≤Δ＋１．因此，显然有犪′（犌）≥χ′（犌）≥Δ．［１］［

7、２］给定一个图犌，令犱（狏）（或犱（狏））表示顶点狏Ｆｉａｍˇｃｉｋ，Ａｌｏｎ等先后分别提出了著名的无圈犌边色数猜想．在犌中的度．度为犽（至少为犽，至多为犽）的顶点称猜想１对任何图犌，犪′（犌）≤Δ＋２．为犽点（犽＋点，犽－点）．对于平面图犎，用犉（犎）表示［３］其面集合，并用犱（犳）（或犱（犳））表示面犳∈犉（犎）１９９１年，Ａｌｏｎ等应用概率方法证明了对任犎收稿日期：２０１４０７０１基金项目：国家自然科学基金资助项目（１１３０１０３５），北京中医药大学卫生服务与卫生经济研究创新团队项目作者简介：王艺桥，女，博士，Ｅｍａｉｌ：ｙｑｗａｎｇ

8、＠ｂｕｃｍ．ｅｄｕ．ｃｎ；舒巧君，女，博士，Ｅｍａｉｌ：ｓｈｕｑｉａｏｊｕｎ＠１６３．ｃｏｍ．引文格式：王艺桥，舒巧君．平面图的无圈边