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.