Software Journal

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.