0 votes

Can you color this graph, such that every vertex receives some color, no two adjacent vertices receive the same color, and number colors used is minimized?

in Graph Theory by AlgoMeister (1.6k points)
edited by

3 Answers

+1 vote
 
Best answer

I've read about Backtracking Method, and here is my try: 

by AlgoMeister (920 points)
selected by
I like the answer.  So, you can basically color this graph using 4 colors?  (Green, Blue, Purple, Yellow)?
I think I can color this graph with 3 colors only if I changed the Yellow to Purple. I just realized that it works also :)
OK, if you can change the yellow to purple and resubmit, I can accept the answer.
I just submitted the updated Graph.
Now my question is: How do you attach images to these answers???

:)
By clicking on the "attach image" button. :-)
Yes, I clicked on "attach image" as Prof. Amrinder said, but first I uploaded the image here https://imgsafe.org/ , then copied the link. I am not sure if there is a simple way to do it through this blog directly?
Thank you! Yes, it seems like 'Attach Image' doesn't attach images directly from our local machine? I tried adding the URL to my local machine with it not doing anything. Thank you Amal for suggesting imgsafe!

If someone knows the steps to do it directly from our PC, please do let us know.
+2 votes

Using the greedy algorithm, we start with 1 color - quickly seeing that it won't work. With 2, I was able to fill out 4 circles before seeing that the next circle I fill in will cause the one afterwards to be adjacent to the same colored ones. With 3 colors, I found the following solution (I was not able to attach an image here... so I attempted to do it with spaced letters. Hopefully my formatting stays the same when I submit the answer). 

                            R

             G                         Y

  Y                                               G

                           G

  R                                               R

                 G                 Y

by AlgoStar (416 points)
+1 vote

If we start from the initial vertex, we can assign it a color (say blue)
As we keep traversing through the graph, we assign alternate colors and check for common edge between them.

The graph has 3-chromatic number. The image is shown below.

by (128 points)
edited by

Related questions

The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...