Polyhedral studies on vertex coloring problems
Many variants of the vertex coloring problem have been de ned, such as precoloring extension, μ-coloring, (γ ; μ)-coloring, and list coloring. These problems are NP-hard, as they generalize the classical vertex coloring problem. On the other side, there exist several families of graphs for which som...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Español |
| Publicado: |
2013
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/94550 |
| Aporte de: |
| id |
I19-R120-10915-94550 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Español |
| topic |
Ciencias Informáticas Vertex coloring problem |
| spellingShingle |
Ciencias Informáticas Vertex coloring problem Delle Donne, Diego Marenco, Javier Polyhedral studies on vertex coloring problems |
| topic_facet |
Ciencias Informáticas Vertex coloring problem |
| description |
Many variants of the vertex coloring problem have been de ned, such as precoloring extension, μ-coloring, (γ ; μ)-coloring, and list coloring. These problems are NP-hard, as they generalize the classical vertex coloring problem. On the other side, there exist several families of graphs for which some of these problems can be solved in polynomial time. The standard integer programming model for coloring problems uses a binary variable xvc for each vertex v and each color c to indicate whether v is assigned c or not. An extension of this model considers binary variables wc for each color c to indicate whether color c is used or not. In this work we study this formulation for the polynomial cases of the coloring problems mentioned above. In particular, we prove that if the classical vertex coloring problem yields an integer polytope for a family of graphs, then the same holds for μ-coloring, ( γ; μ)-coloring, and list coloring over the same family. We prove that the polytope associated to these problems over trees is integer and that adding the clique inequalities, the resulting polytope is integer over block graphs also. Finally, we give a new family of facet-inducing valid inequalities for the standard formulation and we provide empirical evidence suggesting that this family completely describes the polytope associated to these problems over cycles (and probably cactii graphs). |
| format |
Objeto de conferencia Resumen |
| author |
Delle Donne, Diego Marenco, Javier |
| author_facet |
Delle Donne, Diego Marenco, Javier |
| author_sort |
Delle Donne, Diego |
| title |
Polyhedral studies on vertex coloring problems |
| title_short |
Polyhedral studies on vertex coloring problems |
| title_full |
Polyhedral studies on vertex coloring problems |
| title_fullStr |
Polyhedral studies on vertex coloring problems |
| title_full_unstemmed |
Polyhedral studies on vertex coloring problems |
| title_sort |
polyhedral studies on vertex coloring problems |
| publishDate |
2013 |
| url |
http://sedici.unlp.edu.ar/handle/10915/94550 |
| work_keys_str_mv |
AT delledonnediego polyhedralstudiesonvertexcoloringproblems AT marencojavier polyhedralstudiesonvertexcoloringproblems |
| bdutipo_str |
Repositorios |
| _version_ |
1764820491550326786 |