摘要 : A simple polynomial time algorithm to compute the chromatic index of graphs which can be made bipartite by deleting a vertex is presented. An analysis of this algorithm shows that for such graphs, the chromatic index is the roundu... 展开 A simple polynomial time algorithm to compute the chromatic index of graphs which can be made bipartite by deleting a vertex is presented. An analysis of this algorithm shows that for such graphs, the chromatic index is the roundup of the fractional chromatic index. This algorithm is used as a subroutine in an algorithm of Perkovic and Reed for edge coloring graphs which runs in polynomial expected time. 收起