Artículo
The minimum chromatic violation problem: A polyhedral approach
Braga, M.; Delle Donne, D.; Escalante, Mariana Silvina
; Marenco, J.; Ugarte, María Elisa; Varaldo, María del Carmen
![Icon](/themes/CONICETDigital/images/conicet.png)
Fecha de publicación:
07/2020
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known k-partition problem.
Palabras clave:
CHROMATIC VIOLATION
,
GRAPH COLORING
,
K-PARTITION
,
POLYHEDRAL STUDY
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - ROSARIO)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - ROSARIO
Citación
Braga, M.; Delle Donne, D.; Escalante, Mariana Silvina; Marenco, J.; Ugarte, María Elisa; et al.; The minimum chromatic violation problem: A polyhedral approach; Elsevier Science; Discrete Applied Mathematics; 281; 7-2020; 69-80
Compartir
Altmétricas