Feasible edge colorings of trees with cardinality constraints (Q1579549)

The following two extensions of the well-known regular edge colouring are considered. The first imposes cardinality constraints by fixing the number of times each colour can be used and the second restricts the set of possible colours that each edge can receive. The authors prove that both extensions are polynomially solvable for trees with maximum degree bounded by a constant. It is known that determining whether a given graph has an edge colouring satisfying the above constraints is a NP-complete problem, even if restricted to general bipartite multigraphs.