0
$\begingroup$

How would I do A,B,and C fo the following graph.enter image description here

A. For A I used the greedy algorith. So I did $v_1=1,v_2=1,v_3=1,v_4=1,v_5=2,v_6=2,v_7=3,v_8=4$

So I got that the chromatic coloring is 4.

C. For C I said no because we know for every graph G the chromatic number will always be less than or equal to 1 plus the the largest degree in the graph and $1+\Delta=4$ so there cannot be a coloring with more than four colors using greedy.

B. I think there is a different ordering using different ordering that uses fewer color but I canot find it.

$\endgroup$
3
  • $\begingroup$ the problem with the ordering is, that for node $v_8$, all three nodes around it already are coloured in a different colour. Try to find an ordering where this does not happen $\endgroup$
    – Stefan
    Nov 21, 2017 at 23:17
  • 3
    $\begingroup$ you should be able to get an ordering using only 2 colours (as this is a tree) $\endgroup$
    – Stefan
    Nov 21, 2017 at 23:18
  • 1
    $\begingroup$ your answers to a and c look good for me :) $\endgroup$
    – Stefan
    Nov 21, 2017 at 23:19

1 Answer 1

Reset to default
1
$\begingroup$

Intuition says if you do it bad then do it conversely. :-) The greedy algorithm directed by the inverse order $v_8,\dots, v_1$ produces a two-color coloring.

$\endgroup$
1
  • 1
    $\begingroup$ Ok that makes sense thank you $\endgroup$
    – Fernando Martinez
    Nov 22, 2017 at 18:49

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.