Structure of hereditary graph classes and their consequences

许多重要的图论问题，如最小顶点着色、最大团和最大稳定集一般都是NP-完全的（这表明这些问题可能没有多项式时间算法），但对于某些类型的图，其结构可以利用，可以在多项式时间内解决。对于遗传图类（即在导出子图下封闭的图类），我们对分解定理感兴趣：我们如何将图分解为它的基本构建块，使得（1）困难问题可以在这些基本图上容易地解决，以及（2）基本图的解决方案可以组合起来给出原始图的解决方案。一个简单的分解定理，这种范式很好地工作是狄拉克的弦图的特征，它指出，如果一个图是弦，那么它要么是一个团，要么它有一个团割集。遗传图类最著名的分解定理可能是由Maria Chudnovsky、Neil Robertson、Paul Seymour和Robin托马斯在2006年发表的，它解决了克劳德·伯格关于完美图的一个长期猜想。特别地，证明了图G是完美的当且仅当G既不包含奇洞也不包含奇反洞作为导出子图。这就给完美图的多项式时间识别算法让路了。对于完美图，最小顶点着色、最大团和最大稳定集可以在多项式时间内求解。然而，该算法使用椭球方法。它仍然开放是否有可能解决这些问题在多项式时间内使用纯粹的组合方法。对完美图的研究开启了许多关于遗传图类的其他有趣问题，例如激发了对偶无洞图的研究;这类图在结构上与完美图类非常相似。虽然多项式时间算法是已知的识别和寻找最大团在偶数无孔图，找到一个最大的稳定集和最小顶点着色的复杂性仍然是开放的。为了更好地理解无偶洞图类，我们将考虑它的一些子类，并试图理解它们的结构如何在算法中被利用。

Many important graph-theoretic problems such as minimum vertex colouring, maximum clique, and maximum stable set are NP-complete in general (suggesting that there are likely no polynomial-time algorithms for these problems), but can be solved in polynomial time for certain classes of graphs whose structure can be exploited. For hereditary graph classes (i.e. classes of graphs closed under taking induced subgraphs), we are interested in decomposition theorems: how might we decompose a graph into its basic building blocks such that (1) hard problems can be easily solved on these basic graphs, and (2) the solutions for the basic graphs may be combined to give a solution for the original graph. A simple decomposition theorem where this paradigm works nicely is Dirac's characterisation of chordal graphs, which states that if a graph is chordal then it is either a clique or it has a clique cutset. Possibly the most famous decomposition theorem for hereditary graph classes was published in 2006 by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas, which resolved a long-standing conjecture of Claude Berge concerning perfect graphs. In particular, it was shown that a graph G is perfect if and only if G contains neither an odd hole nor an odd antihole as an induced subgraph. This gave way to a polynomial-time recognition algorithm for perfect graphs. It is also known that minimum vertex colouring, maximum clique, and maximum stable set can be solved in polynomial time for perfect graphs. However, this algorithm makes use of the ellipsoid method. It remains open whether it is possible to solve these problems in polynomial time using purely combinatorial methods. This research on perfect graphs opened up many other interesting questions about hereditary graph classes, and for instance motivated the study of even- hole-free graphs; a class which is structurally quite similar to the class of perfect graphs. Although polynomial-time algorithms are known for recognising and finding maximum cliques in even-hole-free graphs, the complexity of finding a maximum stable set and a minimum vertex colouring remain open. Towards a greater understanding of the class of even-hole-free graphs we will consider some of its subclasses and try to understand how their structure can be exploited in algorithms.