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