Introduction to Graph Colorings
What is a Graph?
A graph consists of a set of vertices (or nodes) connected by edges. Graphs can represent various structures in mathematics, computer science, and reallife applications.
A graph on 6 vertices and 6 edges (left) and a graph on 5 vertices and 10 edges (right).
Network graph of flight routes in the USA.
Social media graph, where users are
represented by vertices and edges are
placed between users who are friends.
Graph Colorings
A graph coloring is an assignment of colors to the vertices of a graph in such a way that no two adjacent vertices share the same color. We can use numbers or actual colors to color the vertices of a graph to create a graph coloring.
Graph colorings have applications in many optimization problems, particularly in scheduling and assignment, as well as in various computer science fields such as data mining, image segmentation, clustering, image capture, and networking.
Chromatic Number of a Graph
A graph coloring of a graph always exists, as we can simply assign every vertex a distinct color. However, a more interesting problem is to determine the least number of colors in which one can obtain a graph coloring for a particular graph. This is known as the chromatic number of a graph.
Application Example: Graph colorings can be applied to scheduling university final exams. Each course is a vertex, and edges connect courses with shared students, indicating their exams cannot overlap. The goal is to assign the fewest time slots (colors) so that no connected courses share the same slot. The minimum number of slots required is the graph’s chromatic number, which helps create an efficient, conflictfree exam schedule.
Chromatic Polynomial of a Graph
A graph can have multiple valid colorings, depending on the number of available colors and how they are assigned to the vertices. For any positive integer q, a proper vertex qcoloring, or simply a qcoloring, of a graph G is a graph coloring of G using at most q colors. The chromatic polynomial of G, denoted P(G, q), counts the number of possible qcolorings of G.
The mathematician, George David Birkhoff, first defined the chromatic polynomial in 1912 in his attempt to prove the Four Color Theorem, which states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Birkhoff showed that P(G, q) is always a monic polynomial in q, the degree of which is the number of vertices in the graph.
A fourcolored map of the states of the United States (ignoring lakes and oceans).
Examples of Chromatic Polynomials:
Let q be a positive integer.

The Empty Graph, Eₙ, has n vertices and no edges. Since Eₙ has no edges, we can color each of the n vertices with any of the q colors; the choices are completely independent. Thus, P(Eₙ, q) = qⁿ.

The Complete Graph, Kₙ, has n vertices and an edge between any two vertices. Label the vertices v₁,…,vₙ, and color them individually in the given order. When we color the first vertex v₁, no other vertices have been colored, and we can use whichever of the q vertice we like. However, when we go to colour v1 we note that it is adjacent to v0, and so whatever colour we used for v0 we can't for v1, and so we have k−1 colours to choose for v1


Continuing in this way, we see that since all the vertices are adjacent, they all most have different colours. So when we go to colour vi,

we have already coloured vo,…,vi−1 with i different colours, and we can't use any of these to colour vi, and so we have k−i choices to colour vi.


Putting it all together, we see that: