哈林图的弱边面染色

Weakly Edge-face Coloring of Halin Graphs

设G=(V,E,F)是一个无环的连通平面图,其中V表示点集,E表示边集,F表示面集.对于任意的两条相邻边e_1和e2,如果它们关联同一个面且在该面的边界上连续出现,那么称e_1和e2是面相邻的.图G是弱边面k-可染的是指存在一个映射π:EUF→{1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.平面图G的弱边面染色数是指G是弱边面k-可染的数k的最小值,用_(ef)(G)表示.2016年,Fabrici等人猜想:每个无环且无割边的连通平面图是弱边面5-可染的.本文我们给出此猜想的一个充分条件,即证明:哈林图是弱边面5-可染的,其中上界5是最好可能的.

Let G = （V, E, F） be a connected, loopless plane graph, with vertex set V, edge set E, and face set F. If el and e2 are consecutively adjacent with the same face, then we say that el and e2 are facially adjacent. A plane graph G is called weakly edge-face k-colorable if there is a mapping π ： E∪F → {1, 2, …… , k} 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 k such that G has a weakly edge-face k-coloring. In 2016, Fabrici conjectured that every connected, loopless, bridgeless plane graph is weakly edge-face 5-colorable. In this paper, we proved that Halin graphs are weakly edge-face 5-colorable. Moreover, the upper bound 5 is best possible.