We assigned the problem of showing that 3COLOR is NP-complete, meaning that unless P=NP, there is no polynomial time algorithm to determine whether a given graph is 3-colorable. The classical reduction is from 3-SAT, via some clever gadgets.

One student had the idea that clique numbers could be used to resolve graph coloring questions. This is partly right: if a graph contains a K4 (a 4-clique), it is certainly not 3-colorable. What about the other direction?

Well, let's put it this way: testing whether a graph contains a K4 is a polynomial-time procedure (the brute-force search is O(n^4)). So either we've just proved P=NP, or... there exist graphs that don't contain a K4, yet are not 3-colorable. Can anyone exhibit one?

Subscribe to:
Post Comments (Atom)

## 6 comments:

Take two cycles C5, each is 3-colorable but not 2-colorable. Add any possible edge with one endpoint in the first cycle and one endpoint in the second cycle.

The resulting graph is not 3-colorable.

Thanks Gianluca! Thanks a nice example.

I remember from a combinatorics class I took in Hungary several years ago that there's a theorem that there exist graphs with arbitrarily high chromatic number and girth (size of smallest cycle). It's really quite surprising. I don't remember how the construction goes at all any more, except that it was easier to prove the statement by induction using hypergraphs rather than just graphs.

Thanks Kenny!

I don't know how surprised I am by that fact. To be sure, it's aesthetic and deep, but I just don't have enough combinatorial intuition to be "surprised" by graph-theoreic results. Anyone have a reference for the result Kenny quotes?

hi,

the example gianluca gave is incorrect, as it IS three colorable.

it is true, however, that large cliques are not neccessary to force a high chromatic number. Using the Borsuk Ulam theorem I can show that there exists a graph with arbitrarily large chromatic number and ODD girth (minimal size of odd cycle). since any clique > 2 contains a cycle of length 3 (a triangle) this is more than sufficient to show that there are graphs of arbitrarily high chromatic number and no clicques at all.

Thanks Amitai...

I really should figure out how to do a "recent comments" bar on the side... I end up missing good ones otherwise...

Post a Comment