- | ||||
|
![]()
|
On forests, stable sets and polyhedras associated with clique partitions
Denis Cornaz (cornaz Abstract: Let $G=(V,E)$ be a simple graph on $n$ nodes. We show how to construct a partial subgraph $D$ of the line graph of $G$ satisfying the identity: $\overline \chi(G)+\alpha(D)=n$, where $\overline \chi(G)$ denotes the minimum number of cliques in a clique partition of $G$ and $\alpha(D)$ denotes the maximum size of a stable set of $D$. This is based on correspondences between the cliques partitions and the clique-connecting forests of $G$. We use this to develop a cutting-plane algorithm for the graph coloring problem that is tested on random and DIMACS benchmark graphs. Keywords: Graph coloring, maximum stable set, polytope. Category 1: Combinatorial Optimization Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: Download: [Postscript] Entry Submitted: 03/14/2006 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |