Topics in Graph Theory

图表提供了一种有用的结构来表示广泛领域的许多现实世界网络，例如社交媒体中的友谊链接、互联网上服务器之间的物理连接以及生态系统中的捕食者-猎物关系。这些图表的结构在局部和全局层面上通常都很重要。例如，图中给定大小的团的存在是局部性质，而图的色数是全局性质，但两者通常都是感兴趣的。这两个性质也清楚地联系在一起，一个图的色数至少和最大团的大小一样大。因此，人们很自然地会问，一个色数很大的图是否一定有一个大团。情况并非如此：我们可以构造没有三角形的色数任意高的图(这最初是由Tutte在20世纪40年代证明的)。然而，给出一些关于本地结构的附加信息，我们可以将两者联系起来。例如，Chudnovsky，Robertson，Seymour和Thomas在2006年证明的著名的强完美图定理说，对于一个没有奇洞和没有奇反洞的图，色数等于最大团的大小。一个例子是Gya fas在20世纪80年代提出的一系列著名的猜想，这些猜想最近得到了证明：考虑没有奇孔的图、没有长孔的图、或者在每个剩余类mod 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.