Topics in Graph Theory

Graphs provide a useful structure to represent many real-world networks across a wide range of areas with examples including friendship links in social media, physical connections between servers on the Internet and the predator-prey relationships of an ecosystem. The structure of these graphs is often important on both the local and global level. For example, the presence of a clique of a given size in the graph is a local property, whereas the chromatic number of the graph is a global property, but both are often of interest. These two properties are also clearly linked, the chromatic number of a graph is at least as large as the size of the largest clique. It is therefore natural to ask whether a graph with a large chromatic number must have a large clique. This is not the case: we can construct graphs with arbitrarily high chromatic number which are triangle-free (this was originally proved by Tutte in the 1940s). However, given some additional information about the local structure, we can link the two. For example, the famous Strong Perfect Graph Theorem, proved by Chudnovsky, Robertson, Seymour and Thomas in 2006, says that, for a graph with no odd holes and no odd antiholes, the chromatic number equals the size of the largest clique.

In the last few years, there has been rapid progress on similar questions. One example is a well-known sequence of conjectures made by Gyarfas in the 1980s that have recently been proved: it is enough to consider graphs with no odd holes, or graphs with no long hole, or even graphs that do not have holes of lengths in every residue class mod k. There are a number of new techniques available, and it seems likely that it should be possible to push them further to prove more refined results about the local structure of graphs with large chromatic numbers. It also opens up further questions on what can be said about the constraints that local and global structure impose upon each other.

The proposed research will look to find new relationships between the local structure and global structure of graphs and to improve numerical bounds in cases where some relationship has already been shown. To obtain these results we will begin by applying existing techniques and methods to prove different links between the local structure and global structure. The research will then look to develop new methods to find more links and to improve already existing bounds. The results are likely to require a combination of extremal, structural and probabilistic methods.

This research falls into the EPSRC Mathematical Sciences area and, in particular, classes as extremal combinatorics, an area EPSRC is looking to maintain as an area of key UK strength.