双外平面图的边面染色

On the Edge-Face Coloring of Double-Outer Planar Graph

双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上.证明了对于最大度至少是6的双外平面图,有Xef(G)≤Δ(G)+1,其中Δ(G)是G的最大度.

A double outer planar graph is aplanar graph,which can be embedded in the plane in such a way that all the vertices of planar grapharelocatedintheboundaryoftwofaces.IfGisadouble outerplanargraphwithΔ(G) ≥6,thenXef(G)≤Δ(G)+1,whereΔ(G)isthemaximumdegreeofG.