Edge-colourings and Hamilton decompositions of graphs

A graph consists of a set of vertices, some of which are joined by edges. So every network like the internet gives rise to a graph. Moreover, many timetable scheduling problems can be modelled as graph colouring problems. Unfortunately, graph colouring problems are usually very hard in the sense that it is unlikely that there exists an efficient algorithm for solving them. So one tries to find natural conditions which guarantee the existence of good colourings. This has turned into an important area which has received much attention. However, many fundamental questions remain unsolved. The aim of the project is to solve several of these, based on a new notion of robustly decomposable graphs which we have developed recently. This method will also apply to long-standing problems on decompositions of graphs into Hamilton cycles. These problems in turn have applications to the famous Travelling Salesman Problem.

Graphs consist of vertices, some of which are connected by edges. Over the past few years, their study has become increasingly important, as they can be used to model problems arising in a surprising variety of different situations. Some prominent examples include the web graph (where the vertices represent webpages and the edges represent links between the pages), the network formed by neurons in the brain, and social networks (where the vertices represent people).

Further important examples are (i) graph colourings, which can be used to model e.g. timetabling problems as well as frequency assignment problems and (ii) the travelling salesman problem, where one seeks the shortest round trip connecting a set of cities in a network. Both (i) and (ii) are of considerable practical importance and are related to the objectives in the proposed research. Reaching these objectives will give significant further insights into the nature of these problems.

The focus of the proposed research is not about designing and implementing algorithms for practical problems. However, as mentioned above, it will help to give a better understanding of the basic theory underpinning some of these practical applications. This is of significant interest in itself and may lead to further advances in the design of algorithms for these problems. As explained in the Case for Support and the section on Pathways to Impact, we also intend to investigate these algorithmic aspects as part of the project and follow on research.

The questions we intend to answer are very natural (as can be seen from e.g. the fact that they were asked by leading researchers a long time ago). Since graphs are such basic objects, it is important to be able to answer these questions. Moreover, it is often the case that the tools developed for solving such questions can later be adapted to more realistic (and so more complicated) settings.

Correspondingly, the main immediate impact will be towards the academic community. As described in the section on Academic Impact, there is a wide range of research groups, both in the UK and overseas who would benefit from the proposed research and who would be in a position to develop it further after the completion of the project. So as described in the Section on Pathways to Impact, we will be disseminating our results as widely and efficiently as possible in order to speed up this process.