EPSRC logo

Details of Grant 

EPSRC Reference: EP/J008087/1
Title: Edge-colourings and Hamilton decompositions of graphs
Principal Investigator: Osthus, Professor D
Other Investigators:
Kuehn, Professor D
Researcher Co-investigators:
Project Partners:
Department: School of Mathematics
Organisation: University of Birmingham
Scheme: Standard Research
Starts: 01 June 2012 Ends: 30 September 2014 Value (£): 192,447
EPSRC Research Topic Classifications:
Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
05 Sep 2011 Mathematics Prioritisation Panel Meeting September 2011 Announced
Summary on Grant Application Form
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.
Key Findings
No information has been submitted for this grant.
Potential use in non-academic contexts
No information has been submitted for this grant.
No information has been submitted for this grant.
Sectors submitted by the Researcher
No information has been submitted for this grant.
Project URL:  
Further Information:  
Organisation Website: http://www.bham.ac.uk