Um estudo do politopo e dos limites inferiores gerados pela formulação de coloração dos representantes

Detalhes bibliográficos
Ano de defesa: 2005
Autor(a) principal: Campos, Victor Almeida
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/18654
Resumo: The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value.