EPSRC Reference: 
EP/J008087/1 
Title: 
Edgecolourings and Hamilton decompositions of graphs 
Principal Investigator: 
Osthus, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

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: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

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 longstanding 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 nonacademic contexts 
No information has been submitted for this grant.

Impacts 
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 