| Abstract | 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 the 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 a longstanding and challenging open
question. In this paper we investigate graphs with small diameter. For graphs with diameter at most 2,
we provide the rst subexponential algorithm for 3-coloring, with complexity 2
O
(
p
n
log
n
)
, which is
asymptotically the same as the currently best known time complexity for the graph isomorphism
problem. 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, even for the case of triangle-free graphs. Namely we prove that for
every
"
2
[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 use three di erent ampli cation
techniques of our hardness results, in order to obtain for every
"
2
[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 2
O
(min
f
;
n
log
g
)
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 algorithm is the rst
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
"
2
[
1
2
;
1). |
