Algorithmic graph theory

这项研究方案一般是关于图论的算法方面的，有三个特定的主题：优化算法，证明算法和结构图论。图的四个经典优化问题需要寻找：最优着色、最优团覆盖、最大团和最大稳定集。我们将尝试解决有限类图的问题，例如没有奇洞的图，或者没有规定长度的诱导路的图。在没有规定长度的诱导路的图类上，这些问题是介绍本科生和研究生研究算法图论的一个很好的途径。通常，通过建立给定图的某些结构性质来解决优化问题。 认证算法是一种生成证书的算法，每次输出都能证明它没有受到实现错误的影响。例如，用于识别平面图G的证明算法要么产生G的平面嵌入，要么产生证明G不是平面的两个Kuratowski图之一。我们最近提出的对无P5图G进行3-着色的多项式时间证明算法，要么是G的3-着色，要么是G的一个显然不是3-可着色的子图。我们将继续研究色数较大的限制图。 在结构图论中，人们研究具有一定约束的图，例如不包含另一个图作为导出子图的条件。Erdos和Hajna的一个猜想指出，如果图G不包含有限图H作为导出子图，则G在G的点数中有一个团或稳定的大小多项式集，其中多项式的次数仅取决于H。我们将研究一族这样的猜想。

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. A certifying algorithm is one that produces a certificate with each output that proves that it has not been compromised by an implementation bug. For example, a certifying algorithm for recognizing a planar graph G produces either a planar embedding of G, or one of the two Kuratowski graphs proving that G is not planar. Our recent polynomial-time certifying algorithm for 3-coloring a P5-free graph G produces either a 3-coloring of G, or a subgraph of G that is clearly not 3-colorable. We will continue our investigation for restricted graphs with larger chromatic number. In structured graph theory, one studies graphs with certain restriction such as the condition of not containing another graph as induced subgraphs. A conjecture of Erdos and Hajnal states that if a graph G does not contain a finite graph H as induced subgraph, then G has a clique or stable set of size polynomial in the number of vertices of G, where the degree of the polynomial depends only on H. We will study a family of such conjectures.