Abstract:
A Generalization of the Graph Coloring Problem
This paper presents a generalization of the graph coloring problem. We study its properties and generalize some well-known bounds and definitions.We propose a generalization of perfect graphs and analize the complexity of the problem. An
heuristic is developed to seek "good" solutions and we report their results for random graphs. An IP formulation allows us to evaluate the heuristic in small dimension instances.