Structural graph theory for colouring algorithms and network reliability

我打算继续研究图的结构，网络的数学模型。我的研究兴趣可以分为两个主要领域，这取决于图是建模一个动态网络，其中某些组件可能会失败，还是一个静态网络。对于静态图形，我的动机是应用于调度、物流和优化资源分配，以开发有效的认证算法来为图形族着色。如果一组图只包含有限数量的（k+1）个临界图，则可以通过搜索（k+1）个临界图作为输入图的诱导子图来实现确定k-可着色性的多项式时间算法。如果找到（k+1）关键图，则可以将其作为证书返回，以快速验证输出。因此，为了开发用于图族着色的有效证明算法，我将研究许多族中k-临界图的结构表征。我的首要任务是证明一个二分定理，其中图H对于所有k值只有有限个k临界H-free图。Chudnovsky, Goedgebeur， Schaudt和Zhong最近的工作以及我最近与Hoàng和Sawada的工作表明，对于所有正整数n，H =P4+nP1时，唯一剩下的未知情况。除了这个二分法，我计划对各种图G和H，特别是G=2P2，进行临界（G，H） free图的分类。这是由于许多图族包含相同的无限无2p2图族这一事实。在这一领域的成功将导致新的多项式时间证明算法，这将有助于相应的着色算法的复杂度二分法，或者新的高度结构化的无限关键图族。技术将包括结构图理论和计算机搜索穷举生成的混合。动态图的一个突出模型是顶点（或边）以某种概率p随机独立地起作用。可靠性定义为图具有某些感兴趣的属性的概率，例如与连通性、支配数和cop数相关的属性。最大化图的可靠性在电信、社交网络和网络安全领域都有应用。如果一个图在给定族的所有图中具有最大的信度，则该图是一致最可靠的（UMR）。对UMR图进行分类可以设计最佳网络，即使组件故障随时间而变化。我计划继续使用组合和分析技术对各种可靠性模型下的UMR图进行分类。关于多项式解析理论的经典结果（如高斯和卢卡斯，rouch<s:1>和Möbius的定理）预计将有优雅的应用，就像它们在我以前的工作和其他关于可靠性的工作中一样（如Brown和Colbourn， Royle和Sokal和Wagner的工作）。

I intend to pursue research on the structure of graphs, the mathematical models for networks. My research interests can be divided into two main areas depending on whether the graph is modelling a dynamic network, where certain components may fail, or a static network. For static graphs, I am motivated by applications to scheduling, logistics, and optimizing resource allocation to develop efficient certifying algorithms to colour families of graphs. If a family of graphs contains only a finite number of (k+1)-critical graphs, then a polynomial-time algorithm to determine k-colourability can be implemented by searching for (k+1)-critical graphs as induced subgraphs of the input graph. If a (k+1)-critical graph is found, then it can be returned as a certificate to quickly verify the output. Therefore, to develop efficient certifying algorithms for colouring families of graphs, I will look at the structural characterizations of k-critical graphs in many families. My top priority is to prove a dichotomy theorem classifying for which graphs H there are only finitely many k-critical H-free graphs for all values of k. Recent work of Chudnovsky, Goedgebeur, Schaudt and Zhong together with my recent work with Hoàng and Sawada imply that the only remaining unknown case is when H=P4+nP1 for all positive integers n. In addition to this dichotomy, I plan to classify critical (G,H)-free graphs for various graphs G and H, especially for G=2P2. This is motivated by the fact that many families of graphs contain the same infinite family of 2P2-free graphs. Success in this area will either lead to new polynomial-time certifying algorithms, which will be useful toward a corresponding complexity dichotomy for colouring algorithms, or new highly structured infinite families of critical graphs. Techniques will include a hybrid of structural graph theory and exhaustive generation by computer search. A prominent model for a dynamic graph is where vertices (or edges) are functional independently at random with some probability p. Reliability is defined as the probability that the graph has some property of interest, such as properties related to connectedness, domination number, and cop number. Maximizing the reliability of a graph has applications to telecommunication, social networks, and cybersecurity. A graph is uniformly most reliable (UMR) if it has greatest reliability among all graphs in a given family. Classifying UMR graphs allows for the design of an optimal network, even as component failures change over time. I plan to continue to classify UMR graphs under a variety of reliability models using combinatorial and analytic techniques. Classical results on the analytic theory of polynomials (such as the theorems due to Gauss and Lucas, Rouché and Möbius) are expected to have elegant applications as they have in my previous work and in other work on reliability (such as in the work by Brown and Colbourn, Royle and Sokal and Wagner).