外平面图的弱完备染色

作者：陈敏^*; 杨建民; 张豪; 王依婷

来源：运筹学学报, 2021, 25(01): 132-136.

DOI：10.15960/j.cnki.issn.1007-6093.2021.01.013

• 扇形图
• 外平面图
• 弱完备染色
• 弱完备色数
• 最大度

假设G=(V,E,F)是一个平面图。如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻。图G的一个弱完备k-染色是指存在一个从VUEUF到k色集合{1,…,k}的映射,使得任意两个相邻点,两个相邻面,两条面相邻的边,以及VUEUF中任意两个相关联的元素都染不同的颜色。若图G有一个弱完备k-染色,则称G是弱完备k-可染的。平面图G的弱完备色数是指G是弱完备k-可染的正整数k的最小值,记成Xvef(G)。2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱完备7-可染的。证明外平面图满足猜想,即外平面图是弱完备7-可染的。

• 单位
  浙江师范大学