Title: On the Hardness of 4-coloring a 3-colorable graph
| Speaker: | Akshay Ramachandran |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract: A consequence of the PCP theorem is that it is NP-hard to approximate the chromatic number of a general graph to within \n^{1-\eps} for any constant epsilon. On the other hand, we have seen results that allow us to color a 3-colorable graph with far fewer than n colors. In this talk we will discuss two constructions ([KLS20], [GK04]) that prove hardness of 4-coloring a 3-colorable graph. Both start from the hardness of approximating the clique number, but the former requires the PCP theorem, whereas the latter requires a much weaker hardness result. This will lead to a discussion of the relationship between inapproximability of coloring and PCP constructions: there are implications in both directions and so it is interesting to understand whether PCPs are intrinsic to these hardness results or artifacts of the current proof techniques.