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.