|
|||||
|
|
On a generalization of the Gallai-Roy-Vitaver theorem to the bandwidth coloring problem |
|
| Authors: | Bernard Gendron Alain Hertz Patrick St-Louis |
| Affiliation: | a Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada b CIRRELT, Canada c Département de mathématiques et de génie industriel, École Polytechnique de Montréal, Canada d GERAD, Canada e GIRO Inc., Canada |
| Abstract: | We generalize to the bandwidth coloring problem a classical theorem, discovered independently by Gallai, Roy and Vitaver, in the context of the graph coloring problem. Two proofs are given, a simple one and a more complex one that is based on a series of equivalent mathematical programming models. |
| Keywords: | Graph coloring problem Bandwidth coloring problem Mathematical programming |
| 本文献已被 ScienceDirect 等数据库收录！ | |