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 )

Citation:

Download: [Postscript]

Entry Submitted: 03/14/2006
Entry Accepted: 03/14/2006
Entry Last Modified: 03/14/2006

Modify/Update this entry