| EPSRC Reference: |
EP/I01795X/1 |
| Title: |
Clique-width of graphs |
| Principal Investigator: |
Lozin, Professor V |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics |
| Organisation: |
University of Warwick |
| Scheme: |
Standard Research |
| Starts: |
31 August 2011 |
Ends: |
30 August 2014 |
Value (£): |
244,150
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
24 Nov 2010
|
Mathematics Responsive Mode Prioritisation Panel
|
Announced
|
|
|
Summary on Grant Application Form |
|
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.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.warwick.ac.uk |