1
$\begingroup$

graph

My answer: $p(g,k) = k(k-1)^4(k-2)(k-3) $

I'm new to this subject so was hoping if one of you could check my answer. Thanks.

Vertices:

$\endgroup$
16
  • $\begingroup$ Your answer says $p(g,3)=0$ so there are no ways to color it with $3$ colors? But I just did it: I colored the top vertex red, its two neighbors white, the the four bottom vertices alternately red and blue. So I think your answer must be wrong. $\endgroup$
    – bof
    Commented Jun 17, 2016 at 9:45
  • $\begingroup$ Do you know about Decomposition theorem in graph coloring? $\endgroup$ Commented Jun 17, 2016 at 9:53
  • $\begingroup$ @mathlover Nope. Does it have any relevance to finding the chromatic polynomial of a graph? $\endgroup$ Commented Jun 17, 2016 at 10:39
  • $\begingroup$ Yes..See any standard textbook of graph theory under section graph vertex coloring. $\endgroup$ Commented Jun 17, 2016 at 10:50
  • $\begingroup$ @bof So it would be chromatic polynomial = $k^3(k-1)^2(k-3)^2$? or do i plus them together not times? $\endgroup$ Commented Jun 17, 2016 at 13:05

1 Answer 1

2
$\begingroup$

enter image description here

By Maple software, the chromatic polynomial of your graph, $G$, is $P(G,x)=x(x-1)(x^2-2x+2)(x-2)^3$. Its chromatic number is $3$ with vertex coloring $[[2, 5], [1, 3, 6], [4, 7]]$.

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .