外平面图的弱完备染色  

Weakly entire coloring of outerplanar graphs

作　　者：陈敏 杨建民 张豪 王依婷 CHEN Min;YANG Jianmin;ZHANG Hao;WANG Yiting(Department of Mathematics,Zhejiang Normal University,Jinhua 321004,Zhejiang,China)

机构地区：[1]浙江师范大学数学与计算机科学学院,浙江金华321004:

出　　处：《运筹学学报》2021年第1期132-136,共5页Operations Research Transactions

基　　金：国家自然科学基金(No.11971437);浙江省自然科学基金(No.LY19A010015)。

摘　　要：假设G=(V,E,F)是一个平面图。如果e_(1)和e_(2)是G中两条相邻边且在关联的面的边界上连续出现,那么称e_(1)和e_(2)面相邻。图G的一个弱完备k-染色是指存在一个从VUEUF到k色集合{1,…,k}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及VUEUF中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成X_(vef)(G)。2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。Let G=(V,E,F)be a plane graph.If e_(1) and e_(2) are consecutively adjacent with the same face,then we say that e_(1) and e_(2) are facially adjacent.A plane graph G is called weakly entire k-colorable if there is a mapping from V∪E∪F to{1,…,k}such that any facially adjacent edges,adjacent vertices,adjacent faces,and any two incident elements in V∪E∪F receive distinct colors.The weakly entire chromatic number,denoted X_(vef)(G),of G is defined to be the least integer k such that G is weakly entire k-colorable.In 2016,Fabrici et al.conjectured that every connected,loopless,bridgeless plane graph is weakly entire 7-colorable.In this paper,we prove that the conjecture is true for outerplanar graphs.Namely,outerplanar graphs are weakly entire 7-colorable.

关 键 词：扇形图 外平面图 弱完备染色 弱完备色数 最大度 

分 类 号：O157.5[理学—基础数学]