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

Vuskovic 9908681这个美国-巴西合作研究项目将支持肯塔基州大学的Kristina Vuskovic博士与巴西里约热内卢联邦大学数学研究所的塞利纳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.***