关于图边着色的一点注记

A Note on Edge Coloring of Graphs

本文证明了简单图G的边色数(?)(G)满足(?)(G)=(?)(G[F∪N(F)])。这里F={v|d((v)=△(G)}是G的最大度点集,N(F)是F的邻点集,G[S]记G中由S(?)V(G)导出的子图。

We prove that the chromatic index X'(G) of a simple graph G satisfies X'(G)=X'(G[F∪N(F)]) where F={v|d(v)=△(G)}is the set of maximum degree vertices, N(F)is the set of neighbors of F, G[S] denotes the induced subgraph of SV(G).