Algorithms and Almost Tight Results for -Colorability of Small Diameter Graphs

摘要

The -coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter . Moreover, assuming the Exponential Time Hypothesis (ETH), -coloring cannot be solved in time on graphs with vertices and diameter at most . In spite of extensive studies of the -coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most , or at most , has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most , we provide the first subexponential algorithm for -coloring, with complexity . Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood, and we provide a polynomial algorithm for -coloring on graphs with diameter that have at least one articulation neighborhood. For graphs with diameter at most , we establish the complexity of -coloring by proving for every that -coloring is NP-complete on triangle-free graphs of diameter and radius with vertices and minimum degree . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every subexponential asymptotic lower bounds for the complexity of -coloring on triangle-free graphs with diameter and minimum degree . Finally, we provide a -coloring algorithm with running time for arbitrary graphs with diameter , where is the number of vertices and (resp. ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this is the first subexponential algorithm for graphs with and for graphs with and . Due to the above lower bounds of the complexity of -coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is , where , as its time complexity is and the corresponding lower bound states that there is no -time algorithm.