外平面图的弱边面染色

假设G是一个平面图.如果e1和e2是G中两条相邻边且在关联的面的边界上连续出现,那么称e1和e2面相邻.图G的一个弱边面κ-染色是指存在映射π:E∪F→{1,…,κ},使得任意两个相邻面、两条面相邻的边以及两个相关联的边和面都染不同的颜色.若图G有一个弱边面κ-染色,则称G是弱边面κ-可染的.平面图G的弱边面色数是指G是弱边面κ-可染的正整数κ的最小值,记为χef(G).2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文证明了外平面图满足此猜想,即:外平面图是弱边面5-可染的.

Weakly Edge-face Coloring of Outer Plane Graphs

Let G be a plane graph.If e1 and e2 are consecutively adjacent with the same face,then we say that e1 and e2 are facially adjacent.A plane graph G is called weakly edge-faceκ-colorable if there is a mapping π:E∪F→{1,…,κ} such that any two incident elements,adjacent faces and facially adjacent edges receive distinct colors.The weakly edge-face chromatic number of G,denoted by Xef(G),is defined to be the smallest integer κ such that G is weakly edge-face κ-colorable.In 2016,Fabrici et al.conjectured that every connected,loopless,bridgeless plane graph is weakly edge-face 5-colorable.In this paper,we prove that the conjecture is true for outer plane graphs.Namely,outer plane graphs are weakly edge-face 5-colorable.