We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Algorithms and almost tight results for 3-colorability of small diameter graphs.

Mertzios, G.B. and Spirakis, P.G. (2016) 'Algorithms and almost tight results for 3-colorability of small diameter graphs.', Algorithmica., 74 (1). pp. 385-414.


The 3-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 4. Moreover, assuming the Exponential Time Hypothesis (ETH), 3-coloring cannot be solved in time 2o(n) on graphs with n vertices and diameter at most 4. In spite of extensive studies of the 3-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 2, or at most 3, has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most 2, we provide the first subexponential algorithm for 3-coloring, with complexity 2O(nlogn√). Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood, and we provide a polynomial algorithm for 3-coloring on graphs with diameter 2 that have at least one articulation neighborhood. For graphs with diameter at most 3, we establish the complexity of 3-coloring by proving for every ε∈[0,1) that 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 use three different amplification techniques of our hardness results, in order to obtain for every ε∈[0,1) subexponential asymptotic 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 2O(min{δΔ, nδlogδ}) for arbitrary graphs with diameter 3, where n 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 δ=ω(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 of the input graph is δ=Θ(nε), where ε∈[12,1), as its time complexity is 2O(nδlogδ)=2O(n1−εlogn) and the corresponding lower bound states that there is no 2o(n1−ε)-time algorithm.

Item Type:Article
Keywords:3 -Coloring, Graph diameter, Graph radius, Subexponential algorithm, NP-complete, Exponential Time Hypothesis.
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Final published version)
Publisher Web site:
Publisher statement:© The Author(s) 2014. This article is published with open access at This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Date accepted:07 October 2014
Date deposited:27 October 2014
Date of first online publication:21 October 2014
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar