2012/02/21 by Mertzios, George B., Spirakis, Paul G. · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1202.4665
In spite of the extensive studies of the 3-coloring problem with respect to several basic parameters, the complexity status of the 3-coloring problem on graphs with small diameter, i.e. with diameter 2 or 3, has been a longstanding and challenging open question. For graphs with diameter 2 we provide the first subexponential algorithm with complexity 2O(√(nlog n)), which is asymptotically the same as the currently best known time complexity for the graph isomorphism (GI) problem. Moreover, we prove that the graph isomorphism problem on 3-colorable graphs with diameter 2 is GI-complete. Furthermore we present a subclass of graphs with diameter 2 that admits a polynomial algorithm for 3-coloring. For graphs with diameter 3 we establish the complexity of 3-coloring by proving that for every ε ∈ [0,1), 3-coloring is NP-complete on triangle-free graphs of diameter 3 and radius 2 with n vertices and minimum degree δ=Θ(nε). Moreover, assuming ETH, we provide three different amplifications of our hardness results to obtain for every ε ∈ [0,1) subexponential lower bounds for the complexity of 3-coloring on triangle-free graphs with diameter 3 and minimum degree δ=Θ(nε). Finally, we provide a 3-coloring algorithm with running time 2^O(min\δΔ,\fracnδlogδ\) for graphs with diameter 3, where δ (resp. Δ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this algorithm is the first subexponential algorithm for graphs with δ=ω(1) and for graphs with δ=O(1) and Δ=o(n). Due to the above lower bounds of the complexity of 3-coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree if the input graph is δ=Θ(nε), where ε ∈ [1/2,1).