Mixed graph colorings |
| |
| Authors: | Pierre Hansen Julio Kuplinsky Dominique de Werra |
| |
| Affiliation: | (1) Ecole des Hautes Etudes Commerciales, GERAD, Montréal, Québec, Canada;(2) 6, Washington Drive, 07446 Ramsey, NJ, USA;(3) Départment de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, Chaire de Recherche Operationelle, 1015 Lausanne, Switzerland |
| |
| Abstract: | A mixed graphG contains both undirected edges and directed arcs. Ak-coloring ofG is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number  (G) of a mixed graph is the smallestk such thatG admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience. |
| |
| Keywords: | Graph coloring oriented graphs chromatic scheduling |
| 本文献已被 SpringerLink 等数据库收录！ |
|
