On forests, stable sets and polyhedras associated with clique partitions
Denis Cornaz (cornazmath.jussieu.fr)
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 )
Entry Submitted: 03/14/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|