Name
Abstract | ||
|---|---|---|
Certain subgraphs of a given graph G restrict the minimum number χ(G) of colors that can be assigned to the vertices of G such that the endpoints of all edges receive distinct colors. Some of such subgraphs are related to the celebrated Strong Perfect Graph Theorem, as it implies that every graph G contains a clique of size χ(G), or an odd hole or an odd anti-hole as an induced subgraph. In this paper, we investigate the impact of induced maximal cliques, odd holes and odd anti-holes on the polytope associated with a new 0-1 integer programming formulation of the graph coloring problem. We show that they induce classes of facet defining inequalities. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.ipl.2003.11.005 | Inf. Process. Lett. |
Keywords | Field | DocType |
perfect graph,graph coloring,integer programming,graph coloring problem | Perfect graph,Edge coloring,Discrete mathematics,Combinatorics,Fractional coloring,Graph power,Clique graph,Graph factorization,Factor-critical graph,Mathematics,Perfect graph theorem | Journal |
Volume | Issue | ISSN |
89 | 4 | 0020-0190 |
Citations | PageRank | References |
33 | 1.92 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manoel B. Campêlo | 1 | 151 | 19.59 |
| Ricardo C. Corrêa | 2 | 207 | 18.74 |
| Yuri Frota | 3 | 105 | 13.98 |