Clique-width of graphs

点击翻译按钮获取中文摘要

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.