top of page

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 real-life applications.

graphs_edited.jpg

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.

chromaticnumber.jpg

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, conflict-free 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 q-coloring, or simply a q-coloring, 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 q-colorings 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.

fourcolor.jpg

A four-colored map of the states of the United States (ignoring lakes and oceans).

Examples of Chromatic Polynomials:

    Let q be a positive integer.

  1. 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ⁿ.

  2. 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

  3.  

  4. 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,

  5. 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.

  6.  

  7. Putting it all together, we see that:

bottom of page