文章基本信息

标题：On the Hardness of 4-coloring a 3-colorable Graph
本地全文：下载
作者：Venkatesan Guruswami ; Sanjeev Khanna
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does. This highlights a qualitative difference between the known hardness result for coloring 3-colorable graphs and the factor n hardness for approximating the chromatic number of general graphs, as the latter result is known to imply (some form of) PCP theorem. Another aspect in which our proof is different is that using the PCP theorem we can show that 4-coloring of 3-colorable graphs remains NP-hard even on bounded-degree graphs. We point out that such graphs can always be colored using O(1) colors by a simple greedy algorithm, while the best known algorithm for coloring (general) 3-colorable graphs requires n(1) colors. Our proof technique also shows that there is an \eps00 such that it is NP-hard to legally 4-color even a (1−\eps0) fraction of the edges of a 3-colorable graph.
关键词：Approximation Algorithms, Chromatic Number, graph coloring, NP-hardness, PCP