Chromatic polynomial ( $P_{G} (t)$ )

For each positive integer

t

, the chromatic polynomial

P_{G} (t)

counts the proper vertex colourings of a finite graph

G

using a fixed palette of

t

colours.

Table of contents
- Deletion-contraction recurrence for the chromatic polynomial Chromatic polynomial
- Chromatic polynomial after attaching a leaf Chromatic polynomial

Deletion-contraction recurrence for the chromatic polynomial

For a non-loop edge

e

,

P_{G} (t) = P_{G - e} (t) - P_{G / e} (t) .

The first term counts colourings after deleting

e

; the second subtracts those giving its endpoints the same colour, which correspond to colourings of the contraction. Together with

P_{G} (t) = t^{∣ V (G) ∣}

for an edgeless graph, induction proves that

P_{G}

is a polynomial.

Chromatic polynomial after attaching a leaf

Attaching a new leaf to a graph multiplies its chromatic polynomial by

t - 1

, because after colouring the old graph the leaf may receive any colour except its neighbour's.

 Ancestors (6)

 Incoming links (5)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Chromatic polynomial by

Wikipedia Bot  1

The **chromatic polynomial** is a polynomial that encodes the number of ways to color the vertices of a graph using a given number of colors such that no two adjacent vertices share the same color. Specifically, for a graph \( G \), the chromatic polynomial \( P(G, k) \) is defined as the number of ways to color the graph with \( k \) colors. ### Key Properties 1.

 Read the full article

  See all articles in the same topic Create my own version