Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes

Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes

0.00 Avg rating—0 Votes
Article ID: iaor2014924
Volume: 69
Issue: 3
Start Page Number: 494
End Page Number: 500
Publication Date: Jul 2014
Journal: Algorithmica
Authors: ,
Keywords: optimization
Abstract:

We show that the following fundamental edge‐colouring problem can be solved in polynomial time for any given constant B: given a simple graph G, find an edge‐colouring of G where each colour is assigned to at most B edges and which, subject to this condition, has the fewest number of colour classes.

Reviews

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