2012/02/21 by George B. Mertzios, Mertzios, George B., Paul G. Spirakis +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #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 #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1202.4665
25 pages, 10 figures, 2 tables, 1 algorithm
openalex publication_date 2012/02/21 · arxiv created 2012/10/17 · arxiv updated 2012/10/18 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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).