Coloring a graph's vertices with a minimal number of colors is a classic NP-complete problem, but there are many useful polynomial-time approximation algorithms.

A graph is *chromatic number* of a graph is the minimum possible

Determining the chromatic number of an arbitrary graph is one of Karp's famous 21 **NP**-complete problems; a polynomial-time algorithm would imply **P** = **NP**, which is considered unlikely.

Besides its fundamental theoretical importance, minimum vertex coloring has numerous practical applications. (Vertex coloring is colloquially known as *graph coloring*; edge coloring is also studied.) In the *examination scheduling problem*, exams at a university must be scheduled such the number of exam periods is minimized and no student has two exams at once. This can be modeled as a vertex coloring problem: represent each course as a vertex, and add edges between courses that share students. A vertex coloring of this graph maps each course to an exam period; if two courses share students, they must have a different color and therefore must have examinations at different times.

There are many bounds, approximation algorithms, and heuristics for vertex coloring. All planar graphs have a chromatic number of at most 4 and can be 5-colored in polynomial time. Nontrivial trees and bipartite graphs have a chromatic number of 2 and can be easily colored via depth-first search; cycles have a chromatic number of at most 3 and are also easy to color. More generally, it is well-known that *maximum degree* of all the vertices of

In this project, we investigate approximate vertex coloring algorithms for graphs where there is a large gap between the trivial

To generate test cases for the heuristics, we will primarily consider the *Erdős–Rényi random graph model*

Despite this simple construction, Erdős–Rényi random graphs exhibit rich and surprising behavior, perhaps most notably rapid phase transitions. When

Perhaps the simplest graph coloring heuristic is the following: choose an uncolored vertex at random and assign it a color not used by its neighbors, introducing a new color if the vertex's neighbors are using all previously available colors. Repeat this operation until all vertices are colored.

While this algorithm often performs poorly compared to other heuristics, it is a useful baseline. Grimett and McDiarmid show that this algorithm, in expectation, colors Erdős–Rényi random graphs with only twice as many colors as required.

As a simple improvement to the random coloring algorithm, sort the vertices of a graph by degree and color the vertices with largest degree first. Intuitively, this algorithm handles the hardest vertices—that is, the vertices most likely to be constrained by their neighbors—first and thus avoids excessively introducing new colors in some cases.

Brélaz's widely used degree saturation (DSatur) algorithm often performs better than random coloring.*degree saturation* is the number of unique colors used by its neighbors.

**Input:** a graph

**Output:** a coloring of

**Initialization:**

**while**

- Choose the uncolored vertex
v \in G with maximum saturation degree. If more than one vertex has this saturation degree, choose the vertex with maximum degree instead. - Attempt to color
v with the minimum possible color in[1, i] . If this is not possible, introduce colori + 1 and use it to colorv .

While these heuristics are useful in practice, they yield no worst-case asymptotic improvement over simply assigning each vertex its own color. Johnson constructs examples for random coloring and largest-degree-first coloring that use

Not all simple heuristics for vertex coloring have such poor worst-case performance. Johnson and Wigderson describe the *greedy independent set* heuristic, which can color a

**Input:** a graph

**Output:** a coloring of

**Initialization:**

i \leftarrow 1 (current maximum color)W \leftarrow V (the set of uncolored vertices)U \leftarrow V (the set of uncolored vertices in the current greedy independent set)

**while**

- Choose the vertex
v \in U with minimal degree in the subgraph ofG induced byU . Colorv withi . Removev fromW , as it is now colored. - Remove
v and its neighbors from the current greedy independent setU . - If
U is empty, leti \leftarrow i + 1 andU \leftarrow W (initialize a new greedy independent set with a different color).

For any proper coloring, each color corresponds to an *independent set* of vertices—by definition, no two vertices with the same color share an edge. Step 2 maintains a *greedy independent set* in

Nonetheless, this algorithm exhibits better worst-case performance than its competitors. For the first stage of the algorithm, when there are at least

In a 1983 paper, Avi Wigderson introduced an algorithm for coloring 3-colorable graphs with at most

It is easy to achieve a reasonable coloring of a 3-colorable graph with low maximum degree. For instance, if

For graphs with at least

**Input:** a 3-colorable graph

**Output:** a coloring of

**Initialization:**

**while**

- Choose the vertex
v with maximum degree fromG . - Let
H be the subgraph ofG induced by the neighbors ofv . - 2-color
H with colorsi, i + 1 . - Color
v with colori + 2 . - Let
i \leftarrow i + 2 . - Delete
v and its neighbors fromG .

Color any remaining vertices in

**The maximum-degree algorithm.** A graph

**Proof of correctness (sketch).** Why can

It took nearly ten years after its publication for a 3-coloring algorithm beating the "

Just as Wigderson's algorithm for 3-colorable graphs lifts a polynomial-time 2-coloring algorithm, we can create an approximate algorithm for

**Input:** a

**Output:** a coloring of

**Initialization:**

**Base cases: **if

**function**

**while**

- Choose
v \in G with maximum degree. - Let
H be the subgraph ofG induced by the neighbors ofv . - Color
H recursively: callB(k-1, H, i) . Letj be the number of new colors. - Color
v withi + j . Leti \leftarrow i + j . - Delete
v and its neighbors fromG .

Color

The details of showing that the performance guarantee is achieved are complicated and involve a clever application of Jensen's inequality, but the fundamental insight is that we can use an algorithm for

This algorithm only beats the greedy independent set algorithm for graphs of low degree, but the two algorithms can be trivially combined to yield an algorithm that colors a graph with

Garey and Johnson showed in 1976 that no polynomial-time vertex coloring algorithm exists with an approximation factor beter than 2.**NP** = **ZPP**, Wigderson's algorithm for **NP**-complete problems, such as the 0/1 knapsack problem and the subset sum problem, have tight approximations.

Local search, simulated annealing, tabu search, and evolutionary algorithms are popular techniques for heuristically solving a broad range of combinatorial optimization problems. All of these approaches use an *objective function* and a notion of a *solution neighborhood* to guide the search process. Defining a useful objective function and a way of moving between solutions is nontrivial; some definitions allow for improper coloring in intermediate steps and use an objective function that encourages a proper coloring. Johnson et al. considered three different simulated annealing formulations of the vertex and found that, while simulated annealing often performs better than simpler heuristics such as DSatur, there is not a universally superior simulated annealing formulation.

Evolutionary algorithms, which are loosely inspired by biological evolution, maintain a population of solution candidates that is continually improved through *mutation* events (analogous to random DNA mutation) and *crossover* events (analogous to mating). Defining the crossover step is again nontrivial—vertex colorings are fragile, and the combination of two proper colorings might yield an improper coloring. Carefully tailored evolutionary approaches, particularly when combined with local search, are competitive in practice.

Karger et al. give a *semidefinite programming* formulation for 3-coloring and **NP**-hard problem so that it can be expressed as a linear program and then rounding the solution appropriately is a popular approximation technique; Karger's formulation employs a generalization of this method to produce a *vector k-coloring*, which is a relaxed, continuous version of the discrete coloring problem.

For many small instances, it is possible to solve vertex coloring problems exactly despite the hardness of the general problem. One exact technique involves converting a given coloring problem to a *Boolean satisfiability* (SAT) problem. SAT problems are **NP**-complete, but there are many industrial SAT solvers that can handle problem instances with hundreds of thousands of variables.

Converting the **NP**-complete.

Determining the chromatic number of a graph is very hard—the best known algorithms perform only slightly better than the simplest heuristics. Nonetheless, there is a wide range of efficient approaches to graph coloring that often produce good colorings in practice.