Clique-width of graphs

树宽是一个相对年轻的概念，它概括了另一个重要的图参数树宽，在文献中研究了几十年。树宽的概念推广了树宽的概念，即有界树宽的图具有有界树宽。这些图不变量的重要性是由于这样一个事实，即许多问题是NP-困难的一般承认多项式时间的解决方案时，限制到有界树或树宽度的图形。在研究的概念树宽度，可以限制，不失一般性，以图类，这是封闭的下采取子式，因为一个图的树宽永远不会小于它的任何子图的树宽。根据Robertson和Seymour的著名结果，在一个次闭类X中图的树宽是有界的当且仅当X排除（即不包含）至少一个平面图。换句话说，在小闭图族中，平面图构成了唯一的最小的无界宽度图类。没有这样的标准是已知的概念cumber-width，和cumber-width的情况更加复杂。一个问题是，在连通宽度的情况下，对次闭图类的限制不再有效，因为图的连通宽度可以（远）小于其次闭图类的连通宽度。然而，一个图的宽度不能小于它的任何导出子图的宽度，这允许我们将自己限制在遗传类，即，这些图G包含G的所有导出子图.本项目讨论了用无界图宽的最小遗传类来刻画有界图宽图的遗传类族的问题.这个任务通常是不可解的，因为一类无限宽度的图可能包含无限宽度的子类的无限下降链。这些子类的交集称为极限类，最小极限类称为边界类。边界类概念的重要性是由于这样一个事实，即在一个遗传类中，由多个禁止诱导子图定义的遗传类中的簇宽度是有界的当且仅当它不包含任何边界类。所提出的研究的主要目标是确定的边界类的图的家庭的双基因遗传类，即遗传类定义的两个禁止诱导子图。

Clique-width is a relatively young notion generalizing another important graph parameter, tree-width,studied in the literature for decades. The notion of clique-width generalizes that of tree-width in the sense that graphs of bounded tree-width have bounded clique-width. The importance of these graph invariants is due to the fact that numerous problems that are NP-hard in general admit polynomial-time solutions when restricted to graphs of bounded tree- or clique-width.In the study of the notion of tree-width, one can be restricted, without loss of generality, to graph classes which are closed under taking minors, since the tree-width of a graph is never smaller than the tree-width of any of its minors. According to the celebrated result of Robertson and Seymour the tree-width of graphs in a minor-closed class X is bounded if and only if X excludes (i.e. does not contain) at least one planar graph. In other words, in the family of minor-closed graph classes the planar graphs constitute a unique minimal class of graphs of unbounded clique-width. No such criterion is known for the notion of clique-width, and the situation with clique-width is more complicated. One problem is that in the case of clique-width the restriction to minor-closed graph classes is not valid anymore, since the clique-width of a graph can be (much) less than the clique-width of its minor. However, the clique-width of a graph cannot be less than the clique-width of any of its induced subgraphs, which allows us to restrict ourselves to hereditary classes, i.e., those containing with every graph G all induced subgraphs of G.The present project addresses the question of characterizing the family of hereditary classes of graphs of bounded clique-width in terms of minimal hereditary classes of unbounded clique-width. This task is generally unsolvable, since a class of graphs of unbounded clique-width may contain an infinite descending chain of subclasses of unbounded clique-width. The intersection of thesesubclasses is called a limit class, and a minimal limit class is called a boundary class. The importance of the notion of boundary classes is due to the fact that the clique-width in a hereditary class defined by finitely many forbidden induced subgraphs is bounded if and only if it contains none of the boundary classes. The main objective of the proposed research is identification of the boundary classes of graphs for the family of bigenic hereditary classes, i.e. hereditary classes defined by two forbidden induced subgraphs.