Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Lifted, projected and subgraph-induced inequalities for the representatives k-fold coloring polytope

Texto completo
Autor(es):
Campelo, Manoel ; Moura, Phablo F. S. ; Santos, Marcio C.
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: DISCRETE OPTIMIZATION; v. 21, p. 131-156, AUG 2016.
Citações Web of Science: 0
Resumo

A k-fold x-coloring of a graph G is an assignment of (at least) k distinct colors from the set [1, 2,..., x] to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The kth chromatic number of G, denoted by chi(k)(G), is the smallest x such that G admits a k-fold x-coloring. We present an integer linear programming formulation (ILP) to determine chi(k) (G) and study the facial structure of the corresponding polytope P-k (G). We show facets that Pk+1(G) inherits from P-k(G) and show how to lift facets from P-k (G) to Pk+l (G). We project facets of P-1 (G o K-k) into facets of P-k (G), where G o K-k is the lexicographic product of G by a clique with k vertices. In both cases, we can obtain facet-defining inequalities from many of those known for the 1-fold coloring polytope. We also derive facets of P-k (G) from facets of stable set polytopes of subgraphs of G. In addition, we present classes of facet-defining inequalities based on strongly chi(k)-critical webs and antiwebs, which extend and generalize known results for 1-fold coloring. We introduce this criticality concept and characterize the webs and antiwebs having such a property. (C) 2016 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 15/11930-4 - Problemas de particionamento em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Processo FAPESP: 13/19179-0 - Problemas de otimização sobre partição em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Brasil - Doutorado