Algorithms and Almost Tight Results for $$3$$ 3 -Colorability of Small Diameter Graphs
George B. Mertzios, Paul G. Spirakis · Algorithmica · 2014
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 $$2^{o(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 $$2^{O(\sqrt{n\log n})}$$ . 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 $${\varepsilon \in [0,1)}$$ that $$3$$ -coloring is NP-complete on triangle-free graphs of diameter $$3$$ and radius $$2$$ with $$n$$ vertices and minimum degree $$\delta =\varTheta (n^{\varepsilon })$$ . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every $${\varepsilon \in [0,1)}$$ subexponential asymptotic lower bounds for the complexity of $$3$$ -coloring on triangle-free graphs with diameter $$3$$ and minimum degree $${\delta =\varTheta (n^{\varepsilon })}$$ . Finally, we provide a $$3$$ -coloring algorithm with running time $${ 2^{O\left( \min \{\delta \varDelta ,\ \frac{n}{\delta }\log \delta \}\right) }}$$ for arbitrary graphs with diameter $$3$$ , where $$n$$ is the number of vertices and $$ \delta $$ (resp. $$\varDelta $$ ) 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 $${\delta =\omega (1)}$$ and for graphs with $${\delta =O(1)}$$ and $$\varDelta =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 $$\delta =\varTheta (n^{\varepsilon })$$ , where $${\varepsilon \in [\frac{1}{2},1)}$$ , as its time complexity is $${2^{O\left( \frac{n}{\delta } \log \delta \right) } = 2^{O\left( n^{1-\varepsilon } \log n\right) }}$$ and the corresponding lower bound states that there is no $$2^{o\left( n^{1-\varepsilon }\right) }$$ -time algorithm.