权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Clique-width of graphs

图的团宽度

基本信息

批准号：
EP/I01795X/1
负责人：
Vadim Lozin
金额：
$ 31.11万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2011
资助国家：
英国
起止时间：
2011 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FI01795X%2F1
关键词：
Clique width 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.

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