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.