# Introduction

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

This equation is what we are trying to solve here.

**G **is the Graph and 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

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

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

The Chromatic Polynomial formula is:

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.

So

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

The Chromatic Polynomial formula is:

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:

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

The Chromatic Polynomial formula is:

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:

Where 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)

# Combining formulas

Here is when it gets interesting. This is when you combine the formulas together to get the final polynomial formula.

The same way that derivative have rules to combine formulas, there are some here as well.

For two **vertices** **u** and **v** .

is the Graph **G** with the **Edge** between **u** and **v** **removed**.

is the Graph **G** with the **Edge** between **u** and **v** **added**.

is the Graph G with the **vertices** **u** and **v** **combined** into one **vertex**.

Then here is how you can modify graph to transform them into any shape from above:

So you can recursively add, remove and combine vertices to reach shapes that you know.

## Example

With a given graph G:

You will get:

### G – uv

Here you can see one loop, with the formula:

with **n** is 3 here:

The unconnected vertices formula is:

Where **n** here is 1:

Composed:

### G/uv

After combining **u** and **v**, we get:

Which is just a loop:

With 3 vertices:

### All together

# To know more

https://www.wikiwand.com/en/Chromatic_polynomial

http://mathworld.wolfram.com/ChromaticPolynomial.html