The (k,k-1)-coloring problem: a relaxed multicoring

ISABEL MÉNDEZ-DÍAZ; PAULA ZABALA

Warwick

Simposio; International Symposium on Combinatorial Optimization; 2008

This paper presents an integer programming approach for the (k,k-1)-coloring problem, a relaxed version of the multicoloring problem. We propose a Branch-and-Cut algorithm that includes separation heuristics for valid inequalities we could identify by a polyhedral study, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances.