My research interests lie in the area of graph theory and combinatorial optimization. Some of the earlier work involves balanced matrices. Balanced 0,1 matrices are node-edge incidence matrices of balanced hypergraphs, which were introduced by Berge in 1970 as a generalization of bipartite graphs. These matrices have important polyhedral properties, such as, for a balanced 0,1 matrix, the associated set covering, packing and partitioning polytopes are all integral. Also several properties of bipartite graphs generalize to balanced hypergraphs, such as bicoloring and Konig's minimax theorem. In [2] we generalize Hall's bipartite matching theorem to balanced hypergraphs. The notion of 0,1 balanced matrices was extended to 0,± 1 matrices by Truemper in 1982. This class properly includes totally unimodular matrices. In [1] we present a polynomial time recognition algorithm for this class of matrices.
More recently, I have focused on some questions related to perfect and beta-perfect graphs. Chromatic number of a graph G (chi(G)) is bounded from below by the size of its largest clique (omega(G)) and from above by beta(G) = max {delta_H +1 | H is an induced subgraph of G}. A graph G is perfect if, for every induced subgraph H of G, chi(H)= omega(H). A graph G is beta-perfect if, for every induced subgraph H of G, chi(H) = beta(H).
Perfect graphs were introduced by Berge in 1961. At the same time he conjectured that a graph G is perfect if and only if neither G nor its complement contains an odd hole. This is known as the Strong Perfect Graph Conjecture (SPGC) and it remains open to this day. One interesting aspect of perfect graphs is that finding the chromatic number of a graph or the size of its largest clique, problems that are NP-complete in general, for perfect graphs can be solved in polynomial time (a result due to Grotschel, Lovasz and Schrijver). What remains open is whether we can recognize perfect graphs in polynomial time. If the SPGC is true, this question reduces to: can we recognize graphs without odd holes in polynomial time?
beta-perfect graphs are a newer class, introduced by Markossian, Gasparian and Reed in 1994. They are a subclass of graphs without even holes. For beta-perfect graphs there is a simple greedy algorithm which optimally colors the graph in polynomial time. What remains open is whether beta-perfect graphs can be recognized in polynomial time. It would also be of interset to characterize beta-perfect graphs in terms of forbidden induced subgraphs.
In [4] we obtain a structural characterization of even-hole-free graphs in terms of a decomposition theorem, which we then use to obtain a polynomial time recognition algorithm for this class of graphs. We hope to extend this approach to the study of odd-hole-free graphs. A convenient setting for the study of even-hole-free graphs is their generalization to signed graphs. We consider graphs whose edges can be assigned 0,1 weights in such a way that in the resulting graph all chordless cycles have odd weight, these we call odd-signable graphs. In a similar way we generalize odd-hole-free graphs to even-signable graphs. In [3] we characterize graphs that are both odd-signable and even-signable.
In [5] we show that if a graph G contains no even hole and no short-chorded cycle on 6 or fewer vertices, then G is beta-perfect. This generalizes the result of Markossian, Gasparian and Reed who show that if a graph contains no even hole and no short-chorded cycle then it is beta-perfect.
References: