Find the total number of ways of coloring the eight regions

[feesicksman]

Homework Statement

We have a figure which has been divided into 8 regions (A to H) as shown below. Each region must be colored in exactly one color. There are four colors to choose from: yellow, red, green and blue. There is only one other constraint: neighboring regions must not be of the same color.
Find the total number of ways of coloring the regions A to H.

Relevant Equations

I think this problem can be viewed as a vertex coloring procedure (with at most 4 colors) in graph theory.

The eight regions

 

[berkeman]

Please show your efforts to work on the problem. Thank you.

 

[scottdave]

It may help to first work through a smaller, simpler problem.

 

[haruspex]

If you know some graph theory, have you come across chromatic polynomials?

 

[pbuk]

OP has not returned. The solution can be found by elementary counting, I don't think that categorising the problem as graph theory helps.

 

[haruspex]

The solution can be found by elementary counting,

Really? That looks a bit tough to me. Using the deletion-contraction theorem I got 768 quite quickly.
Besides, it would seem the OP has done some graph theory, so likely this question is intended as an exercise in using the theorem.

 

[pbuk]

Really? That looks a bit tough to me. Using the deletion-contraction theorem I got 768 quite quickly.

I got the same answer accumulating the product of 8 numbers in my head, 6 of which are 2:

Spoiler

How many ways can you colour D? (d)
Given a colouring for D, how many ways can you colour E? (e, so what is de?)
Given a colouring for D and E, how many ways can you colour B? (b, so what is deb?)
...

Besides, it would seem the OP has done some graph theory, so likely this question is intended as an exercise in using the theorem.

I'm not so sure - it could just be that they searched the interweb and found "vertex coloring procedure".

Anyway they don't look like they are interested in this any more.

 

[haruspex]

I got the same answer accumulating the product of 8 numbers in my head, 6 of which are 2:

Spoiler

How many ways can you colour D? (d)
Given a colouring for D, how many ways can you colour E? (e, so what is de?)
Given a colouring for D and E, how many ways can you colour B? (b, so what is deb?)
...

I'm not so sure - it could just be that they searched the interweb and found "vertex coloring procedure".

Anyway they don't look like they are interested in this any more.

Very neat. Interestingly, it mirrors the deletion-contraction approach, in reverse order.
To be looking up vertex colouring, the OP first had to recognise the duality between vertices and regions.