US-Brazil Cooperative Research: Graph Decompositions and perfectly Conctractile Graphs

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

Vuskovic 9908681 This US-Brazil collaborative research project will support Dr. Kristina Vuskovic of the University of Kentucky to work with Professor Celina Miraglia Herrera de Figueiredo at the Instituto de Matematica of the Universidade Federal do Rio de Janeiro in Brazil. The researchers will investigate the Perfectly Contractile Graph Conjecture and a possible construction of a polynomial time recognition algorithm for perfectly contractile graphs through the decomposition method. Many diverse applications in graph theory amount to finding the chromatic number of a graph. Unfortunately this problem is NP-complete in general. Perfect graphs are an important class of graphs for which the problem can be solved in polynomial time. However, the existing algorithm uses the ellipsoid method and consequently does not have satisfactory complexity. So it is still of great interest to try to find a combinatorial algorithm for finding the chromatic number of perfect graphs. In an attempt to do so, the class of perfectly contractile graphs emerged. The U.S. PI has expertise in graph decomposition techniques, while the Brazilian PI provides the experience in perfectly contractile graphs. ***