In this paper, we characterize the equistable graphs within the class of EPT graphs, the edge-intersection graphs of paths in a tree. This result generalizes a previously known characterization of equistable line graphs. ...

Trevisan [SIAM J. Comput., 41 (2012), pp. 1769-1786] presented an algorithm for Max-Cut based on spectral partitioning techniques. This is the first algorithm for Max-Cut with an approximation guarantee strictly larger ...

We consider the problem of partitioning a graph into cliques of bounded cardinality. The goal is to find a partition that minimizes the sum of clique costs where the cost of a clique is given by a set function on the nodes. ...

The multilevel graph partitioning strategy aims to reduce the computational cost of the partitioning algorithm by applying it on a coarsened version of the original graph. This strategy is very useful when large-scale ...

Graphs with bounded thinness were defined in 2007 as a generalization of interval graphs. In this paper we introduce the concept of proper thinness, such that graphs with bounded proper thinness generalize proper interval ...

Confirming a conjecture of Gyarfas, we prove that, for all natural numbers k and r, the vertices of every r-edge-colored complete k-uniform hypergraph can be partitioned into a bounded number (independent of the size of ...