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.
Article
View On forests, stable sets and polyhedras associated with clique partitions