Recent Grant Applications
The aim of this project is to apply decomposition methods to the reconstruction conjectures. Our main decomposition tool is the so-called operator decomposition of graphs. This decomposition consists in the representation of graphs as elements of some semi-group and the consideration of a graph in question as a result of action of that semi-group on the set of all graphs. The approach seems to be fruitful because the operator decomposition of graphs showed itself as an effective instrument for the problems connected with the notion of isomorphism.
·
Strongly Perfect Graphs Report 1
Report 2 Report 3
The development of graph theory over the last four decades has been strongly influenced
by the Strong Perfect Graph Conjecture and perfect graphs introduced by Berge
in the early 1960s. The class of perfect graphs is one of the basic concepts in
graph theory and they have interesting applications. The well-known Strong
Perfect Graph Conjecture has been open for about 40 years and various attempts
to prove it have given rise to many powerful methods, important concepts and
interesting results in graph theory. Chudnovsky, Robertson, Seymour and Thomas
have recently proved this conjecture. In 1978 Berge introduced another
important class of graphs called strongly perfect graphs. They form a subclass
of perfect graphs. We will apply a man-computer technique to strongly perfect
graphs and formulate a characterisation conjecture for this class of graphs.
The conjecture will be tested and then proved for some important subclasses.
·
Embedding Graphs on Topological Surfaces (joint with Dr A.
Gagarin) Report 1
Report 2 Report
3
We plan to devise and implement efficient algorithms for detecting projective-planar and toroidal graphs. These algorithms will require special use of the computer data structures. Moreover, we plan to carry out a feasibility study into generalisations of our algorithmic results for graphs embeddable on the surfaces of higher genus, e.g. the Klein bottle. Structural properties of projective-planar and toroidal graphs will also be investigated.
The primary purpose of this proposal is to develop and then data mine a comprehensive database of graph invariants with the aim of producing new insights and theorems in graph theory. Using new analytical techniques from artificial intelligence, we can generate interesting graph-theoretic conjectures by looking for patterns which appear to hold in the database of invariants. As such, it contributes to a growing body of research which uses computers to aid the discovery of new results in graph theory.
The main aim of the proposed
project is to investigate various open problems and conjectures with the help
of GraphLab, a Windows application for graph theory. For example, we intend to
resolve a number of well-known problems connected with the domination
parameters, to study a problem of Bartels and Welsh on the expected number of colours
used in a random colouring, to verify unimodal and log-concavity conjectures
about the coefficients of the chromatic polynomial and the number of forests of
a graph, and to check whether a certain graph polynomial does not distinguish
trees. Moreover, we plan to verify some of the conjectures generated by the
well-known computer program GRAFFITI.