几乎外平面图的边染色

The edge-coloring of almost-outerplanar graphs

若图G存在边e使G -e为外平面图 ,则称G为几乎外平面图 .本文证明了 ,连通几乎外平面图G是第二类的当且仅当G是奇圈或Δ(G) =3且G有一个 2 连通子图G′含有唯一的 2 度点 .同时 ,Fiorni关于外平面图边色数的结论得以推广 .

If a graph G has an edge e such that G-e is outerplanar,then G is called almost-outerplanar graph. In this paper,we prove that a connected almost-outerplanar graph G has the edge chromatic number Δ(G)+ 1 if and only if G is an odd cycle,or Δ(G )=3 and G has a 2-connected subgraph which contains a unique 2-vertex. It generalizes a result of Fiorinis'.