Advances and Applications in Discrete Mathematics
Volume 9, Issue 2, Pages 65 - 81
(April 2012)
|
|
VECTORIAL SOLUTIONS TO LIST MULTICOLORING PROBLEMS ON GRAPHS
Yves Aubry, Jean-Christophe Godin and Olivier Togni
|
Abstract: For a graph G with a given list assignment L on the vertices, we give an algebraic description of the set of all weights w such that G is -colorable, called permissible weights. Moreover, for a graph G with a given list L and a given permissible weight w, we describe the set of all -colorings of G. By the way, we solve the channel assignment problem. Furthermore, we describe the set of solutions to the on call problem: when w is not a permissible weight, we find all the nearest permissible weights Finally, we give a solution to the non-recoloring problem keeping a given subcoloring |
Keywords and phrases: weighted graph, coloration, channel assignment problem. |
|
Number of Downloads: 259 | Number of Views: 728 |
|