[go: up one dir, main page]
Scribd
Upload
291 views7 pages

Decomposition Theorem For Chromatic Polynomial

The document defines the decomposition theorem for chromatic polynomials and provides examples to illustrate its use. The decomposition theorem states that the chromatic polynomial of a graph G can be expressed as the difference between the chromatic polynomials of G - e and G.e, where e is any edge of G. The examples show applying this theorem to find the chromatic polynomial for various small graphs, such as circuits of different lengths, and proving properties of the coefficients in the chromatic polynomial.

Uploaded by

parmar003akash
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
291 views7 pages

Decomposition Theorem For Chromatic Polynomial

The document defines the decomposition theorem for chromatic polynomials and provides examples to illustrate its use. The decomposition theorem states that the chromatic polynomial of a graph G can be expressed as the difference between the chromatic polynomials of G - e and G.e, where e is any edge of G. The examples show applying this theorem to find the chromatic polynomial for various small graphs, such as circuits of different lengths, and proving properties of the coefficients in the chromatic polynomial.

Uploaded by

parmar003akash
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

Definition 5.0.

13 (Decomposition theorem)
Decomposition theorem for chromatic polynomial is

P(G, λ) = P(Ge , λ) − P(Ge0 , λ) = P(G − e, λ) − P(G.e, λ)

Dr.A.Benevatho Jaison MAT1002 September 23, 2022 363 / 375


Example 5.0.14
Show that the chromatic polynomial of a graph consisting of a single circuit of
length n is
Pn (λ) = (λ − 1)n + (λ − 1)(−1)n

Let G be a circuit of length n.


⇒ The number of vertices = number of edges = n.
When n = 3 f (k3 , λ) = λ(λ − 1)(λ − 2)

f (G, λ) = P3 (λ) = (λ − 1)3 + (λ − 1)(−1)3


= (λ − 1)3 − (λ − 1)
= (λ − 1)[(λ − 1)2 − 1]
= (λ − 1)[λ2 − 2λ + 1 − 1]
= (λ − 1)(λ2 − 2λ)
= f (k3 , λ)
Dr.A.Benevatho Jaison MAT1002 September 23, 2022 364 / 375
The result is true for n = 3.
Assume that the result is true for n − 1.
Let G be a circuit of length n and e be any edge of the cycle.
Clearly G.e is a circuit of length (n − 1).
So the result holds for G.e. Therefore,

f (G.e, λ) = (λ − 1)n−1 + (−1)n−1 (λ − 1)

Now, since G is a circuit of length n, G − e is an open walk of length n − 1 and


so it is a tree of n vertices.

f (G − 1, λ) = λ(λ − 1)n−1
We have f (G, λ) = f (G − e, λ) − f (G.e, λ)
= λ(λ − 1)n−1 − (λ − 1)n−1 − (−1)n−1 (λ − 1)
= (λ − 1)n−1 (λ − 1)(−1)n−1
= (λ − 1)n + (λ − 1)(−1)n

Hence, the result.


Dr.A.Benevatho Jaison MAT1002 September 23, 2022 365 / 375
Example 5.0.15
If G is a simple graph of n vertices and q edges then the coefficient of λn−1 in
the chromatic polynomial f (G, λ) is −q.
(OR)
Show that the absolute value of the second coefficient of λn−1 in the chromatic
polynomial Pn (λ) of a graph equals the number of edges in the graph.

We prove the result by induction on the number of edges q.


When q = 0 the graph G is a null graph of n vertices. Therefore,

f (G, λ) = λn = λn − 0.λn−1 + · · ·

Therefore, coefficient of λn+1 = 0 = q.


Thus the result is true in this case.
Let us assume that the result holds good for less than q edges.
Let e be any edge of G.
We know that, G − e and G.e are of (q − 1) edges and so the result holds in
these cases.
Dr.A.Benevatho Jaison MAT1002 September 23, 2022 366 / 375
Since, G − e is of n vertices and G.e of (n − 1) vertices we can take

f (G − e, λ) = λn − (q − 1)λn−1 + · · ·
f (G.e, λ) = λn−1 − (q − 1)λn−1 + · · ·
f (G − e, λ) − f (G.e, λ) = λn − qλn−1 + · · ·
= f (G, λ)

The coefficient of λn−1 = −q


The absolute value = q.

Dr.A.Benevatho Jaison MAT1002 September 23, 2022 367 / 375


Example 5.0.16
Using Decomposition theorem, find the chromatic polynomial of the following
graph

We use the recurrence formula

f (G, λ) = f (G + e, λ) + f (G.e, λ)

Dr.A.Benevatho Jaison MAT1002 September 23, 2022 368 / 375


= k4 + k3

f (G, λ) = f (k4 , λ) + f (k3 , λ)


= λ(λ − 1)(λ − 2)(λ − 3) + λ(λ − 1)(λ − 2)
= λ(λ − 1)(λ − 2)[λ − 3 + 1]
= λ(λ − 1)(λ − 2)2

Dr.A.Benevatho Jaison MAT1002 September 23, 2022 369 / 375

You might also like