EPSRC Reference: 
EP/I01795X/1 
Title: 
Cliquewidth of graphs 
Principal Investigator: 
Lozin, Professor V 
Other Investigators: 

Researcher CoInvestigators: 

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 
Cliquewidth is a relatively young notion generalizing another important graph parameter, treewidth,studied in the literature for decades. The notion of cliquewidth generalizes that of treewidth in the sense that graphs of bounded treewidth have bounded cliquewidth. The importance of these graph invariants is due to the fact that numerous problems that are NPhard in general admit polynomialtime solutions when restricted to graphs of bounded tree or cliquewidth.In the study of the notion of treewidth, one can be restricted, without loss of generality, to graph classes which are closed under taking minors, since the treewidth of a graph is never smaller than the treewidth of any of its minors. According to the celebrated result of Robertson and Seymour the treewidth of graphs in a minorclosed 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 minorclosed graph classes the planar graphs constitute a unique minimal class of graphs of unbounded cliquewidth. No such criterion is known for the notion of cliquewidth, and the situation with cliquewidth is more complicated. One problem is that in the case of cliquewidth the restriction to minorclosed graph classes is not valid anymore, since the cliquewidth of a graph can be (much) less than the cliquewidth of its minor. However, the cliquewidth of a graph cannot be less than the cliquewidth 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 cliquewidth in terms of minimal hereditary classes of unbounded cliquewidth. This task is generally unsolvable, since a class of graphs of unbounded cliquewidth may contain an infinite descending chain of subclasses of unbounded cliquewidth. 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 cliquewidth 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 nonacademic 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 