Edge coloring nearly bipartite graphs

Edge coloring nearly bipartite graphs

0.00 Avg rating0 Votes
Article ID: iaor20003679
Country: Netherlands
Volume: 24
Issue: 1/2
Start Page Number: 11
End Page Number: 14
Publication Date: Feb 1999
Journal: Operations Research Letters
Authors:
Keywords: graph colouring
Abstract:

We give a simple polynomial time algorithm to compute the chromatic index of graphs which can be made bipartite by deleting a vertex. An analysis of this algorithm shows that for such graphs, the chromatic index is the roundup of the fractional chromatic index.

Reviews

Required fields are marked *. Your email address will not be published.