The Library
Boundary properties of graphs
Tools
Korpelainen, Nicholas (2012) Boundary properties of graphs. PhD thesis, University of Warwick.

Text
WRAP_THESIS_Korpelainen_2012.pdf  Submitted Version Download (765Kb)  Preview 
Official URL: http://webcat.warwick.ac.uk/record=b2582711~S1
Abstract
A set of graphs may acquire various desirable properties, if we apply suitable restrictions
on the set. We investigate the following two questions: How far, exactly, must one restrict
the structure of a graph to obtain a certain interesting property? What kind of tools are
helpful to classify sets of graphs into those which satisfy a property and those that do not?
Equipped with a containment relation, a graph class is a special example of a partially
ordered set. We introduce the notion of a boundary ideal as a generalisation of a notion
introduced by Alekseev in 2003, to provide a tool to indicate whether a partially ordered set
satisfies a desirable property or not. This tool can give a complete characterisation of lower
ideals defined by a finite forbidden set, into those that satisfy the given property and to
those that do not. In the case of graphs, a lower ideal with respect to the induced subgraph
relation is known as a hereditary graph class.
We study three interrelated types of properties for hereditary graph classes: the existence
of an efficient solution to an algorithmic graph problem, the boundedness of the graph
parameter known as cliquewidth, and wellquasiorderability by the induced subgraph relation.
It was shown by Courcelle, Makowsky and Rotics in 2000 that, for a graph class, boundedness
of cliquewidth immediately implies an efficient solution to a wide range of algorithmic
problems. This serves as one of the motivations to study cliquewidth. As for wellquasiorderability,
we conjecture that every hereditary graph class that is wellquasiordered by
the induced subgraph relation also has bounded cliquewidth.
We discover the first boundary classes for several algorithmic graph problems, including
the Hamiltonian cycle problem. We also give polynomialtime algorithms for the dominating
induced matching problem, for some restricted graph classes.
After discussing the special importance of bipartite graphs in the study of cliquewidth,
we describe a general framework for constructing bipartite graphs of large cliquewidth. As
a consequence, we find a new minimal class of unbounded cliquewidth.
We prove numerous positive and negative results regarding the wellquasiorderability of
classes of bipartite graphs. This completes a characterisation of the wellquasiorderability of
all classes of bipartite graphs defined by one forbidden induced bipartite subgraph. We also
make considerable progress in characterising general graph classes defined by two forbidden
induced subgraphs, reducing the task to a small finite number of open cases. Finally, we
show that, in general, for hereditary graph classes defined by a forbidden set of bounded
finite size, a similar reduction is not usually possible, but the number of boundary classes
to determine wellquasiorderability is nevertheless finite.
Our results, together with the notion of boundary ideals, are also relevant for the study
of other partially ordered sets in mathematics, such as permutations ordered by the pattern
containment relation.
Item Type:  Thesis (PhD)  

Subjects:  Q Science > QA Mathematics  
Library of Congress Subject Headings (LCSH):  Graph theory  
Official Date:  June 2012  
Dates: 


Institution:  University of Warwick  
Theses Department:  Mathematics Institute  
Thesis Type:  PhD  
Publication Status:  Unpublished  
Supervisor(s)/Advisor:  Lozin, Vadim V.  
Sponsors:  Engineering and Physical Sciences Research Council (EPSRC) ; University of Warwick. Centre for Discrete Mathematics and its Applications (DIMAP)  
Extent:  viii, 131 leaves : ill.  
Language:  eng 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year