## 1. Introduction

In this tutorial, we’ll explore vertex coloring in graphs.

## 2. Vertex Coloring

A graph is a collection of nodes (vertices) and edges such that every edge joins two vertices from . For example:

We look at the problem of coloring all nodes of a loopless graph with unique colors. To clarify, a loopless graph is one in which no node has an edge connecting it to itself.

Vertex (or node) coloring of means finding an assignment that colors each vertex so that no two neighboring vertices have the same color. For instance:

Formally, a proper vertex coloring of is a mapping , where are colors, such that no two adjacent vertices have the same color:

If there’s a proper coloring of a graph with colors, we say that is -colorable.

## 3. Chromatic Number

We define the chromatic number of (denoted by ) as the minimum number of colors required to vertex color . In other words, it’s the smallest such that is -colorable.

### 3.1. Properties

First, for a graph where , it holds that . Second, for a complete graph , since each vertex is connected to the remaining vertices. On similar lines, where is a null graph.

Moving on, if is a sub-graph of , then  . This is intuitive since would need no more colors than because has no more nodes than .

### 3.2. NP-Completeness

Determining the chromatic number for a generic graph is an NP-complete problem.

These problems are of great interest to computer scientists because they arise in many practical applications, but no algorithm with the worst-case polynomial complexity is known to solve them.

### 3.3. Color Classes

The nodes of a -colorable graph can be partitioned into independent sets: . Here, no two vertices in a set are adjacent to each other.

For our vertex-coloring example graph , we have , so and . Both and are independent as and .

## 4. Algorithm

In this section, we present a greedy algorithm for determining the chromatic number of a graph. It isn’t an exact algorithm, which means it returns an upper bound on :




### 4.2. Explanation

Firstly, we set the colors of all the nodes  -1 to denote that all vertices at the start are uncolored (white).

Then, we iterate over the nodes sorted by their degrees. There are options for each node in the beginning (). We disregard the colors assigned to its neighbors and give it the minimal color code remaining in .

After processing all the nodes, the algorithm returns the maximum color code as the chromatic number. Since this is a greedy algorithm, the returned number is only an estimate and should be treated as the upper bound of .

### 4.3. Space and Time Complexity

The time complexity of this algorithm depends on how we implement and . If we use hash tables, the overall time complexity will be .

The space complexity is also because of the upper bound on the number of edges in a graph with nodes.

### 4.4. Example

Let’s check out an example:

Initially, all the nodes are white (). Since there are seven nodes, each vertex in the main loop will start with seven available colors. Let their codes be blue=1, green=2, red=3, pink=4, black=5, brown=6, violet=7.

We start with vertex , which has the highest degree (3). Its neighbors are . All are white, so we color as blue since that’s the minimum of :

Next, we take vertex . Its neighbors are . Since is blue, we disregard the color 1 and assign the minimum of the remaining codes (2):

Now comes the turn of . Its neighbors are . The reasoning is the same as for , so we color it green:

Continuing like this, we color this graph using two colors (blue and green), which gives us .

## 5. Applications

This enables us to run various operations on graphs to solve specific problems.

### 5.1. Exam Scheduling

Here, we consider the problem of scheduling exams in a university. Typically, we have different subjects and will have many students enrolled in each subject. Further, each student can be enrolled in more than one subject, and each subject will have more than one enrolled student.

We need to schedule exams such that no two exams with at least one common student are on the same day. Additionally, we want to schedule all exams in the minimal possible number of days. How do we solve this? Vertex coloring comes to our rescue:

We represent this problem as a graph where we model each subject as a vertex. We introduce an edge between two vertices if the corresponding subjects have at least one student in common. Then, we find the graph’s chromatic number. It’s equal to the minimum number of days necessary to schedule all the exams simultaneously without a clash.

In our example, we’ll have 8 exams over 4 days.