A graph G=(V,E) is called equistable if there exist a positive integer t and a weight function $w:V \longrightarrow \mathbb{N}$ such that S⊆V is a maximal stable set of G if and only if w(S)=t. The function w, if exists, is called an equistable function of G. No combinatorial characterization of equistable graphs is known, and the complexity status of recognizing equistable graphs is open. It is not even known whether recognizing equistable graphs is in NP.#R##N##R##N#Let k be a positive integer. An equistable graph G=(V,E) is said to be k-equistable if it admits an equistable function which is bounded by k. For every constant k, we present a polynomial time algorithm which decides whether an input graph is k-equistable.
['Vadim E. Levit', 'Martin Milanič', 'David Tankus']
On the recognition of k -equistable graphs