Introduction

This article is a simple explanation on how to find the chromatic polynomial as well as calculating the number of color: f( $\inline \fn_cm \lambda$ )

$\inline \fn_cm P(G, \lambda ) = f(\lambda)$

This equation is what we are trying to solve here.

G is the Graph and $\inline \fn_cm \lambda$ is the number of color available.

If you remember how to calculate derivation for function, this is the same principle here. You need to look at your Graph and isolate component and use formula that you need to remember by heart. We will explain them later in this article.

Definition

Vertices is a point or a node of the graph.

Edge is a connection between two Vertices.

List of the Chromatic Polynomial formulas with simple graphs

When graph have 0 edge

$\fn_cm P(G, \lambda ) = \lambda^{n}$

Where n is the number of Vertices.

Python Code:

def chromatic_polynomial(lambda, vertices):
    return lambda ** vertices

Complete Graph

This is a graph which have each of its Vertices connected to all the other Vertices.

Which mean that

$\fn_cm E = V * (V - 1)$

Where E is the number of Edges and V the number of Vertices.

The Chromatic Polynomial formula is:

$Chromatic Polynomial for complete graph$

Where n is the number of Vertices.

Python Code:

import math

def chromatic_polynomial(lambda, vertices):
    return math.factorial(lambda) / math.factorial(lambda - vertices)

For Path

A path is graph which is a “line”. Each Vertices is connected to the Vertices before and after it. This graph don’t have loops, and each Vertices is connected to the next one in the chain.

$\fn_cm E = V - 1$

Where E is the number of Edges and V the number of Vertices.

The Chromatic Polynomial formula is:

$Chromatic Polynomial for path graph$

Where n is the number of Vertices.

Python Code:

def chromatic_polynomial(lambda, vertices):
    return lambda * ( ( lambda - 1) ** (vertices - 1) )

For Cycle / Loop

A cycle or a loop is when the graph is a path which close on itself.

That mean that:

$\fn_cm E = V$

Where E is the number of Edges and V the number of Vertices.

The Chromatic Polynomial formula is:

$Chromatic Polynomial for loop graph$

Where n is the number of Vertices.

Python Code:

def chromatic_polynomial(lambda, vertices):
    return ( lambda - 1 ) ** vertices + (( -1 ) ** vertices) * ( lambda - 1 )

Composed Graph

This is when you have two graph which are not connected by edges.

The Chromatic Polynomial formula is:

$Chromatic Polynomial for composed graph$

Where $\fn_cm G_{i}$ is the Graph number i . And M is the number of Graphs.

Python Code:

from functools import reduce

def chromatic_polynomial(lambda, vertices, graph_chromatic_polynomial*):
     return reduce(operator.mul, map(lambda f: f(lambda, vertices), graph_chromatic_polynomial), 1)