Algorithmic graph theory

本研究计划一般是关于图论的算法方面，有三个特定的主题：优化算法，证明算法和结构化图论。图上的四个经典优化问题要求找到：最优着色、最优团盖、最大团和最大稳定集。我们将尝试解决限制类图上的问题，例如没有奇孔的图，或者没有规定长度的诱导路径的图。对于一类没有规定长度诱导路径的图，这些问题是引导本科生和研究生研究算法图论的一个很好的方法。通常，通过建立给定图的某些结构性质来解决优化问题。

This research proposal is generally about algorithmic aspects of graph theory with three particular themes: optimization algorithms, certifying algorithms and structured graph theory. Four classical optimization problems on graphs require finding: an optimal coloring, an optimal clique cover, a largest clique and a largest stable set. We will attempt to solve the problems on restricted classes of graphs such as graphs without odd holes, or without induced paths of prescribed lengths. On the class of graphs without induced paths of prescribed lengths, these problems are a good way to introduce undergraduate and graduate students to research in algorithmic graph theory. Typically, the optimization problems are solved by establishing certain structural properties of the given graphs.