2-连通的平面图的边面染色

Edge-face coloring of 2-connected plane graphs

一个平面图G的边面色数χ_(ef)(G)是最小的颜色数,使得G中任意两条相邻的边、两个相邻的面、以及两个关联的边和面都染不同的颜色.本文证明了,若G是?≥16的2-连通平面图,则χ_(ef)(G)=?.这改进了已知结果:若G是?≥24的2-连通平面图,则χ_(ef)(G)=?.

The edge-face chromatic number χef（G） of a plane graph G is the least number of colors such that any two adjacent edges, adjacent faces, and incident edge and face have different colors. In this paper, we show that if G is a 2-connected simple plane graph with maximum degree △≥16, then χef（G） = △. This improves a known result that if G is a 2-connected simple plane graph with△≥24, then χef（G） = △.