0
$\begingroup$

I have problem stating "Find total number of ways to color a regular pentagon with 5 colors." If we consider(Exact 5 colors to color the graph) it unlabeled graph then it will be the same to arranging 5 persons around a circular table where chairs are not numbered that is (5-1)!. But for labeled graph i am confused for this pentagon we can color first vertex with 5 and second with 4 and third with 3 so on .. so it is 5!(Wrong!), I think it is recursive problem.

But these are number of ways with exact 5 colors and i am also not sure my approach is correct or not ? Please suggest a good source or hint to learn general solutions for such coloring problems.

My question- "Find total number of ways to color a regular pentagon with 5 colors." It is possible with at least 3 of 5 in general so what is general solution?.

$\endgroup$
  • 1
    $\begingroup$ Usually graphs are required to be coloured such that no two adjacent vertices have the same colour (but vertices that are not adjacent can have the same colour). Is that what's going on here? $\endgroup$ – Ben Millwood Feb 22 '14 at 13:15
  • $\begingroup$ @BenMillwood i know that but how to compute total number of ways ? I know i did it in wrong way. $\endgroup$ – kumar Feb 22 '14 at 13:19
0
$\begingroup$

If you are familiar with the notion of Chromatic Polynomial, this is an easy problem. You just calculate the Chromatic Polynomial of the Cycle $C_5$ : $$C_5=P_5-C_4 \,.$$

If not, here is the standard approach.

The strategy: You color vertices in order. You have 5 choices for vertex 1, 4 for vertex 2, 4 for vertex 3 ...

The problem: How many choices do we have for vertex 5? Note that the answer depends on whether vertices 1 and 4 have the same color or different colors.

The solution: Split the problem in 2: count separately the number of ways of coloring $C_5$ such that $1$ and $4$ have the same color and the number of ways of coloring $C_5$ such that $1$ and $4$ have different colors. Note that in the second case you'll need to split again in 2 and 4 have same or different colors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.