Topics in Graph Theory

图提供了一个有用的结构来表示许多现实世界中的网络，包括社交媒体中的友谊链接，互联网上服务器之间的物理连接以及生态系统中的捕食者-猎物关系。这些图的结构通常在局部和全局层面上都很重要。例如，图中存在给定大小的团是局部性质，而图的色数是全局性质，但两者都经常令人感兴趣。这两个性质也是有明显联系的，图的色数至少和最大团的大小一样大。因此，很自然地要问一个具有大色数的图是否一定有一个大团。事实并非如此：我们可以构造具有任意高色数的无三角形的图（这最初是由Tutte在20世纪40年代证明的）。然而，如果给出一些关于局部结构的额外信息，我们可以将两者联系起来。例如，著名的强完美图定理是由Chudnovsky，Robertson，Seymour和托马斯在2006年证明的，该定理指出，对于一个没有奇洞和奇反洞的图，其色数等于最大团的大小。一个例子是一个著名的序列的magnetures所作的Gyarfas在20世纪80年代，最近已被证明：这是足够的考虑图没有奇洞，或图没有长洞，甚至图没有洞的长度在每个剩余类模k。有一些新的技术，似乎应该有可能进一步推动他们证明更精细的结果与大色数的图的局部结构。它也打开了进一步的问题，可以说什么的限制，当地和全球结构强加于对方，拟议的研究将寻求找到新的局部结构和全球结构的图之间的关系，并改善数值界的情况下，一些关系已经显示。为了得到这些结果，我们将开始通过应用现有的技术和方法来证明局部结构和全局结构之间的不同联系。然后，研究将寻求开发新的方法来找到更多的链接，并改善现有的界限。结果可能需要极值，结构和概率方法相结合。这项研究福尔斯落入EPSRC数学科学领域，特别是极端组合学，EPSRC正在寻找一个领域保持作为一个领域的关键英国实力类。

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.