Sunday, April 15, 2007

A clique bound on coloring numbers?

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?

6 comments:

Gianluca Della Vedova said...

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.

Aryeh said...

Thanks Gianluca! Thanks a nice example.

Kenny said...

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.

Aryeh said...

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?

Anonymous said...

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.

Aryeh said...

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