Week 3 The chromatic polynomial

Question 1

Vertex colouring

Answer 1

A vertex colouring of a graph G= (V,E,ε) using n colours
is a function f: V →{1,2,···,n}satisfying
∀i,j ∈V i∼j= ⇒ f(i) ≠ f(j).

Question 2

Chromatic number

Answer 2

For a graph G, the smallest natural number n for which a
vertex colouring using n colours exists is called the
chromatic number of G, denoted χ(G).

Question 3

Chromatic polynomial

Answer 3

For each natural number n, let P_G(n) denote the number of
vertex colourings of G using n colours. We call P_G the
chromatic polynomial of G.