外平面图的弱完备染色

摘要

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