The Vertex k-cut Problem

Given an undirected graph G = (V, E), a vertex k-cut of G is a vertex subset of V the removing of which disconnects the graph in at least k connected components. Given a graph G and an integer k greater than or equal to two, the vertex k-cut problem consists in finding a vertex … Read more

Solving Vertex Coloring Problems as Maximum Weight Stable Set Problems

In Vertex Coloring Problems, one is required to assign a color to each vertex of an undirected graph in such a way that adjacent vertices receive different colors, and the objective is to minimize the cost of the used colors. In this work we solve four different coloring problems formulated as Maximum Weight Stable Set … Read more

On forests, stable sets and polyhedras associated with clique partitions

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 … Read more