Graph coloring algorithms

• Grant number: 20/09330-7
• Support type: Scholarships in Brazil - Scientific Initiation
• Effective date (Start): November 01, 2020
• Effective date (End): May 31, 2021
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal researcher: Carla Negri Lintzmayer
• Grantee: Wesley Lima de Araujo
• Home Institution: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brazil

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.