Just wrapping up project 2 presentations in the CS 6212 – Algorithms class.  Here is a survey that is open to students.

This was a question in the Design and Analysis of Algorithms (CS 6212) final last night.  I don’t know how the students did, but essentially, one way to create such a graph is take a C5 (a cycle on 5 vertices), that we know requires 3 colors.  Then, to this, we attach a K2 (a simple 2 node connected graph), and connect the two vertices of K2 to each vertex in C5.

This graph requires 5 colors (3 for C5 + 2 other ones that cannot overlap with colors used in C5), and this graph does not have a K5, since the original graph (C5) does not have a triangle.

So far so good. Interesting question – What is the graph with fewest number of vertices, such that it is K5 free, and it’s chromatic number is at least 5? I suspect this is the same graph, but I do not have any proof.

[#cs6212gwu] I have heard a few requests for the answers to the “practice final”. However, I do not provide answers to the practice final, as that allows me to use the practice final as the real final in case I don’t get any time to make one. (If I also gave answers, then I would really NEED to make a new final, as opposed to merely WANT to make a new final.)

The good news is there is absolutely no constraints on how you can obtain answers to the practice final. You can call Sergey Brin and Larry Page (they have this utility called Google, which I hear works kinda ok.) Also, you can call anyone physically (using a cell phone with a voice plan). You can also visit friends and ask them in person. You can put this on Craigslist and offer a $ reward. So, in short, there are no restrictions. Nada. Zilch. Cipher. Nul.

Wait, actually, there is one constraint. You just can’t ask ME! (As the politicians would say, I didn’t lie or make a mistake, I “misspoke”. Alternatively, I can have my office issue a clarification that, “that was not meant to be a factual statement.”)

And that is all I have to say about that.