Structural graph theory for colouring algorithms and network reliability

点击翻译按钮获取中文摘要

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).