Minimum Graph Coloring

Given an undirected graph $G=(V,E)$ , a proper vertex coloring assigns a color to every vertex such that no two adjacent vertices receive the same color.

More formally, if $c(v)$ denotes the color assigned to vertex $v$ , then for every edge $(u,v) \in E$ ,

c(u) \neq c(v).

The goal of Minimum Graph Coloring is to find a proper coloring that uses the smallest possible number of colors. The minimum number of colors required to properly color a graph is called its chromatic number.

Throughout this specification, Minimum Graph Coloring is abbreviated MGC.

Your goal throughout the project will be to investigate algorithms involving graph colorings. The specific algorithmic tasks required at each stage are described in the corresponding checkpoint.

Before implementing your algorithms, review the project-wide Program Interface and Input Files specifications.

Graph Assumptions

MGC instances use simple, undirected graphs.

Vertices are numbered consecutively beginning with 0: $V=\{0,1,\ldots,n-1\}$ .
Graphs are not necessarily connected.
Isolated vertices may appear.
Every vertex must be assigned exactly one color.

The standard unweighted graph formats and supplied input routines are described on the Input Files page.

Example

The same graph and its edge-list representation are shown side-by-side below.

The number in parentheses beside each vertex indicates its assigned color.

Example graph                                  example-01.txt

               1 (1)                               5 5
              /     \                               0 1
             /       \                              1 2
          0 (0)     2 (0)                           2 3
             \       /                              3 4
              \     /                               4 0
               4 (2) --- 3 (1)

This coloring uses three colors:

c(0)=0,\quad c(1)=1,\quad c(2)=0,\quad c(3)=1,\quad c(4)=2.

Every pair of adjacent vertices has a different color, so this is a valid coloring.

This graph is an odd cycle and cannot be properly colored using only two colors. Therefore, the coloring shown above is a minimum coloring and the chromatic number of the graph is 3.

For comparison, the assignment

[0,1,0,1,0]

is not a valid coloring because vertices 0 and 4 are adjacent and are both assigned color 0.

MGC Solution Format

MGC uses minimum_graph_coloring as its project-wide problem identifier.

The solution object contains the number of colors used and the color assigned to each vertex:

"solution": {
  "num_colors": 3,
  "colors": [0, 1, 0, 1, 2]
}

The entry colors[v] gives the color assigned to vertex $v$ . Therefore, the colors list must contain exactly one entry for every vertex in the graph.

Color numbers begin with 0. If a solution uses $k$ colors, the colors must be numbered consecutively:

0,1,\ldots,k-1.

The actual numbers used as color labels have no special meaning. Only whether two vertices have the same or different colors matters.

num_colors must equal the number of distinct colors appearing in the colors list.

Using the common project interface,

python src/solve.py example-01.txt \
    --problem minimum_graph_coloring \
    --algorithm exhaustive

could produce:

{
  "problem": "minimum_graph_coloring",
  "algorithm": "exhaustive",
  "instance": "example-01",
  "solution": {
    "num_colors": 3,
    "colors": [0, 1, 0, 1, 2]
  },
  "statistics": {}
}

Your program is required to report only one minimum coloring. If an instance has multiple minimum colorings, any one of them is acceptable; your program does not need to enumerate all optimal solutions.

Different assignments of color numbers may represent equivalent colorings. For example, replacing every color 0 with color 1 and every color 1 with color 0 does not create a fundamentally different coloring.

Solution Verifier

Your Checkpoint 2 implementation must provide:

from course.common.graph import Graph


def is_valid_coloring(graph: Graph, colors: list[int], k: int) -> bool:
    ...

in:

src/student/problems/minimum_graph_coloring/verifier.py

This is the verifier for the decision version of Minimum Graph Coloring. It returns True exactly when colors is a proper coloring of graph that uses at most k distinct colors.

For the example graph:

is_valid_coloring(graph, [0, 1, 0, 1, 2], 3)   # True
is_valid_coloring(graph, [0, 1, 0, 1, 2], 2)   # False: uses 3 colors
is_valid_coloring(graph, [0, 1, 0, 1, 0], 3)   # False: edge (0,4) conflicts

A certificate must assign exactly one nonnegative integer color to every vertex. Adjacent vertices must receive different colors. The verifier does not need to require consecutive color labels; for example, [4,7,4,7,9] can be a valid certificate using three colors. Solver output, however, must normalize its labels to 0,1,...,k-1.

The verifier checks the supplied certificate and threshold. It does not determine whether the coloring is minimum and must not call a solving algorithm.

Gradescope may import and test is_valid_coloring() independently of src/solve.py.

Checkpoint 2 Exhaustive Baseline

Checkpoint 2 uses the project-wide complete-candidate enumeration model. For Minimum Graph Coloring, try k = 1, 2, 3, .... For each k, enumerate complete assignments of all n vertices to the k available colors. Each completed assignment is then tested with is_valid_coloring().

Once the first feasible k is found, that coloring is optimal because every smaller number of colors has already been exhausted.

The Checkpoint 2 baseline should not reject a coloring while it is still only partially assigned, choose the next vertex adaptively, prune impossible partial assignments, or use branch-and-bound. Those are the kinds of improvements explored beginning in Checkpoint 3.

Checkpoint 3 Improved Exact Search

A natural improved exact strategy assigns colors incrementally and rejects a partial coloring as soon as it creates a conflict. More sophisticated exact methods may choose the next vertex using degree or saturation information and may use bounds to avoid trying color counts that cannot succeed.

For example, a recursive search can maintain a partial color assignment and, for the next vertex, consider only colors not already used by its colored neighbors. This avoids generating many complete assignments that the Checkpoint 2 exhaustive baseline would generate and reject only at the end.

These are examples rather than required implementations. Your improved solver must remain exact and you must justify why any work it avoids cannot eliminate an optimal coloring.

Checkpoint 3 Lower Bound

Minimum Graph Coloring is a minimization problem, so the required polynomial-time bound is a lower bound on the chromatic number:

from course.common.graph import Graph


def lower_bound(graph: Graph) -> int:
    ...

in:

src/student/problems/minimum_graph_coloring/bound.py

If the optimum chromatic number is $OPT$ , a valid result must satisfy

\texttt{lower\_bound}(G) \le OPT.

One useful source of lower bounds is a clique that you can find in polynomial time: if you find a clique of size $r$ , then at least $r$ colors are required. The bound routine does not need to find a maximum clique; that would itself be an NP-hard problem. A greedily constructed clique, a detected triangle, or another polynomial-time argument can provide a valid lower bound.

You are not required to use a particular technique, but the returned value must be valid and computed in polynomial time.

Course Benchmark Suites

The supplied Minimum Graph Coloring benchmark manifest is located at:

benchmarks/minimum_graph_coloring/manifest.json

The required suites use the common experiment tool, for example:

python tools/run_experiments.py --suite exact_frontier
python tools/run_experiments.py --suite quality_known
python tools/run_experiments.py --suite heuristic_scale
python tools/run_experiments.py --suite structure

Exact frontier

The exact-search frontier contains three graph families with known chromatic numbers by construction:

odd cycles — sparse graphs with chromatic number 3;
complete graphs — K_n requires exactly n colors; and
planted four-color graphs — each graph contains a K_4 but all other edges are placed between four known color classes, proving that the chromatic number is exactly 4.

The default local exact-frontier timeout is 15 minutes per algorithm/instance. After an algorithm times out on one member of a frontier family, larger members of that same family are skipped for that algorithm.

The Gradescope timeout is intentionally shorter. Gradescope is a bounded automated check; the local CP4 frontier is where you investigate when your exact algorithm becomes impractical.

Heuristic quality and scale

The known-quality and scale suites use planted k-colorable graphs that also contain a K_k. Therefore their chromatic number is exactly k, even for the largest instances. The scale suite extends through 5,000 vertices.

Structural experiment

The required structural study holds both graph size and optimum fixed:

$n=300$ ;
$OPT=8$ .

Each graph is built from eight planted color classes and contains an explicit K_8. Additional edges are added only between different color classes, so an 8-coloring always exists. The benchmark varies the probability of these additional cross-class edges, producing low-, medium-, and high-density graphs while keeping both n and the chromatic number fixed.

This lets you investigate whether edge density affects heuristic solution quality, runtime, variation across seeds, or the tightness of your lower bound without simultaneously changing graph size or the optimum.

See:

benchmarks/minimum_graph_coloring/structure.md

for the full description.