Increasing the chromatic number of a random graph

Noga Alon, Benny Sudakov

Abstract: What is the minimum number of edges that have to be added to the random graph $G = G_{n,0.5}$ in order to increase its chromatic number $\chi(G)$ by one percent? One possibility is to add all missing edges on a set of $1.01\chi(G)$ vertices, thus creating a clique of chromatic number $1.01\chi(G)$. This requires, with high probability, the addition of $\Theta(n^2 / \log^2 n)$ edges. We show that this is tight up to a constant factor, consider the question for more general random graphs $G_{n,p}$ with $p = p(n)$, and study a local version of the question as well.

Introduction

In the study of random graphs, the chromatic number $\chi(G)$—the minimum number of colors required to color the vertices such that no two adjacent vertices share a color—is a fundamental property. For the Erdős–Rőnyi random graph $G_{n,p}$, where $n$ vertices are connected with probability $p$, the chromatic number is well-characterized, typically concentrated around $n / (2 \log_b(np))$.

This paper investigates the resilience of this property. Specifically, we ask: how many edges must an adversary add to a random graph to significantly increase its chromatic number? This question probes the stability of the graph's structure. If an adversary wants to force the use of, say, 1% more colors, can they do so by adding a few strategic edges, or must they perform a massive overhaul of the graph's topology?

The Resilience Problem

Prior research by Sudakov and Vu (2008) established initial bounds on this problem, but a significant gap remained between the known upper bounds (what an adversary could do) and the lower bounds (what an adversary must do). The most intuitive way to increase the chromatic number is to create a large clique—a subset of vertices where every possible edge exists. Creating a clique large enough to require $1.01\chi(G)$ colors requires adding $\Theta(n^2 / \log^2 n)$ edges.

Alon and Sudakov aim to prove that this "clique-building" strategy is, in fact, the most efficient method possible. This involves exploring both global resilience (the total number of edges added anywhere in the graph) and local resilience (the number of edges added to any specific vertex).

Methodology

The authors employ the probabilistic method to demonstrate that random graphs are remarkably stubborn. The core of the proof rests on a new technical lemma regarding the distribution of independent sets—subsets of vertices containing no edges. In a valid coloring, each color class is an independent set. To keep the chromatic number low, one must be able to partition the graph into a small number of large independent sets.

To prove that an adversary cannot easily destroy all large independent sets, the authors use advanced concentration inequalities, including a $4\mu_0$-Lipschitz function and Alon-Kim-Spencer inequalities. They demonstrate that large independent sets in $G_{n,p}$ are "uniformly distributed" across the graph. No matter which edges an adversary adds, there will almost always remain a large independent set that remains relatively "clean" (containing very few of the newly added edges).

By employing an iterative greedy coloring process—repeatedly identifying and removing these "clean" independent sets—the authors show that the total number of colors required does not rise significantly until a massive number of edges have been added.

Key Results

Global Resilience

Theorem 1.2 establishes that for a random graph with edge probability $p$, an adversary must add $\Omega(n^2 / \log^2 n)$ edges to increase the chromatic number by a constant factor $\epsilon$. This result is "tight," matching the order of magnitude required to build a large clique. This significantly improves upon previous lower bounds (such as $np^2/\log^5 n$), providing a definitive answer to the global resilience question.

Local Resilience

Theorem 1.3 addresses the local version of the problem. Even if an adversary is allowed to add edges such that each vertex's degree increases by up to approximately $n / (\log n \log \log n)$, the chromatic number remains essentially unchanged (within a $1+\epsilon$ factor). This suggests that even distributed, local perturbations are insufficient to easily break the graph's colorability.

Discussion and Future Work

The findings reinforce a recurring theme in combinatorics: random structures are often more robust against local perturbations than carefully engineered ones. The "uniformity of independence" ensures that the graph's fundamental properties are difficult to shift.

However, some questions remain:

  1. The $\log \log n$ Gap: In the local resilience result, a small logarithmic factor $(\log \log n)$ persists. The authors conjecture this is a technical artifact of the proof and that the result should hold without it.
  2. Lower-Order Increases: This work focuses on increasing $\chi(G)$ by a percentage. Determining the minimum edges needed to increase the chromatic number by a fixed integer (e.g., from $k$ to $k+1$) is a much more difficult problem related to the concentration of the chromatic number, which remains an open challenge.
  3. Constant Optimization: The authors did not prioritize optimizing absolute constants (such as the $2^{-12}$ factor in Theorem 1.2), leaving the door open for more precise numerical refinements in future studies.

Summary updated

Abstract

What is the minimum number of edges that have to be added to the random graph G = G n,0.5 in order to increase its chromatic number = (G) by one percent? One possibility is to add all missing edges on a set of 1.01 vertices, thus creating a clique of chromatic number 1.01. This requires, with high probability, the addition of (n 2 / log 2 n) edges. We show that this is tight up to a constant factor, consider the question for more general random graphs G n,p with p = p(n), and study a local version of the question as well.
BibTeX
@article{alon2010increasing,
  author = {Noga Alon and Benny Sudakov},
  title = {{Increasing the chromatic number of a random graph}},
  journal = {Journal of Combinatorics},
  year = {2010},
  doi = {10.4310/joc.2010.v1.n4.a1},
}

Loading related content...

Figure