Graph Theory 12

Describe what is The chromatic polynomial χG,

Let G be a graph. We define the function

χG : N → N as

it is the number of different k proper colrongs.
χG(k) = |{φ : V(G) → [k] | φ is proper}|.

what is edge contraction?

Let G be a graph and let e ∈ E(G) with e = uv. We define G/e as the graph where e iscontracted.

state and proof edge contraction/deletion relationship.

Let G be a graph with e ∈ E,

then χG(k) = χG−e(k) − χG/e(k).

Proof. Let k ∈ N and write e = uv.

The set of proper colorings of G − e partitioned:

Sk = {φ : φ(u) = φ(v)} and Dk = {φ : φ(u) ≠ φ(v)}.

Observe that | Sk | = χG/e(k) and | Dk | = χG(k). The result follows.

Prove that The chromatic polynomial is a

polynomial

what is true for two disjoint graphs chromatic polynomial

Let G, H be graphs then χG∪H(k) = χG(k) ⋅ χH(k).

Proof. There is a natural bijection between

and

{proper k-colorings of G ∪ H}
{proper k-colorings of G} × {proper k-colorings of H}.

Let Pn be the path on n vertices. Then what is chromatic polynomial

χPn(k) = k(k − 1)^n−1

Let Cn be the cycle on n vertices. Then what is chromatic polynomial

χCn(k) = (k − 1)^n + (−1)^n(k − 1)

Suppose G can be written as the union of two graphs G1, G2 whose intersection is a single vertex. Then χG(k) = (1/k) ⋅ χG1(k) ⋅ χG2(k).

For any j ∈ [k] the number of proper k-colorings of G, G1, and G2 where v gets assigned

j are

(1/k) ⋅ χG(k),

(1/k) ⋅ χG1(k) and

(1/k) ⋅ χG2(k)

respectively. We thus have:

(1/k) ⋅ χG(k) = [(1/k) ⋅ χG1(k)] ⋅ [(1/k) ⋅ χG2(k)]

This simplifies to χG(k) = (1/k) ⋅ χG1(k) ⋅ χG2(k).