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

这项美巴合作研究项目将支持肯塔基大学的Kristina Vuskovic博士与巴西巴西联邦大学数学研究所的Celina Miraglia Herrera de Figueiredo教授合作。研究人员将研究完全可收缩图猜想，并通过分解方法可能构造一个多项式时间的完全可收缩图识别算法。图论中许多不同的应用都是求图的色数。不幸的是，这个问题通常是np完全的。完美图是一类重要的图，它的问题可以在多项式时间内解决。然而，现有的算法采用椭球体方法，因此复杂度不理想。因此，寻找一种求完美图的色数的组合算法仍然是一个很有意义的问题。为了做到这一点，出现了一类完全可收缩图。美国PI在图分解技术方面拥有专业知识，而巴西PI提供了完美收缩图的经验

Vuskovic9908681This 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.***