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.
Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes
RIZZI, ROMEO;
2014-01-01
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
