Feasible edge colorings of trees with cardinality constraints
type: Item
instance of: scholarly article
title: Feasible edge colorings of trees with cardinality constraints
zbMATH Open document ID: 0963.05057
DOI: 10.1016/S0012-365X(00)00006-6
author: N. V. R. Mahadev
author: Dominique De Werra
author: Alain Hertz
author: Daniel Kobler
published in: Discrete Mathematics
publication date: 2001-06-28T00:00:00Z
review text: 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.
reviewed by: Jozef Fiamčík
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 1506818
zbMATH Keywords: cost
zbMATH Keywords: timetabling
zbMATH Keywords: edge colouring
zbMATH Keywords: cardinality constraints
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00006-6
OpenAlex ID: W2062819334
description: scientific article; zbMATH DE number 1506818