Graph coloring algorithms

Abstract

A problem is of combinatorial optimization if it has as objective finding solutions on a domain that minimize or maximize a goal function. These characteristics are inherent to several important problems in the real world that come from different areas. Unfortunately, many combinatorial optimization problems are NP-hard, which leaves us with almost no hope to find efficient algorithms to solve them. The mathematical structure known as graph is used to model several combinatorial optimization problems, such as graph coloring problems, whose goal is is to find an specific rotulation for the vertices of the graph. Graph coloring problems are very important, because they can represent situations in which we have conflicts between objects and we want to separate them in groups according to some criteria, such as allocation problems. The objective of this project is to enlarge the research experience of the student in combinatorial optimization and design of algorithms by studying graph coloring problems and related algorithms.