| EPSRC Reference: |
EP/J008087/1 |
| Title: |
Edge-colourings and Hamilton decompositions of graphs |
| Principal Investigator: |
Osthus, Professor D |
| Other Investigators: |
|
| Researcher Co-investigators: |
|
| Project Partners: |
|
| Department: |
School of Mathematics |
| Organisation: |
University of Birmingham |
| Scheme: |
Standard Research |
| Starts: |
01 June 2012 |
Ends: |
31 May 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 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.
|
|
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 |