Probabilistic Analysis of the Chromatic Polynomial

Network congestion is a pertinent issue in many fields, from satellite interference to transport route timings. To tackle such issues, networks are often modeled as graphs, collections of vertices joined by edges. The chromatic polynomial is a key function in graph theory, counting the number of ways to colour a graph with k colours such that no adjacent vertices have the same colour. This provides a measure of how sensitive the network is to congestion. However, in the case of dynamic networks that change with time, a probabilistic analysis is needed. Our work analyses the chromatic polynomial in the Erdős–Rényi model, where each edge appears independently at random with probability p. We provide formulas for the expectation and variance of the resulting chromatic polynomial that are more theoretically and computationally efficient. Using these formulas, we compute these polynomials explicitly for some simple classes of graphs. We also derive results on the first few terms of the expected and variance polynomials. These results allow us to make estimates on the expectation and variance, leading to “confidence interval” bounds which can prove useful in risk assessment of real networks. Our findings, supported by computational simulations, show promise to be extended to other models of random graphs, providing researchers with a versatile tool which can be used for a range of applications.