We present a deterministic algorithm producing the number of
$k$-colourings of a graph on $n$ vertices in time
$2^nn^{O(1)}$.
We also show that the chromatic number can be found by a
polynomial space algorithm running in time $O(2.2461^n)$.
Finally, we present a family of ... more >>>

We investigate the hardness of approximating the longest path and
the longest cycle in directed graphs on $n$ vertices. We show that
neither of these two problems can be polynomial time approximated
within $n^{1-\epsilon}$ for any $\epsilon>0$ unless
$\text{P}=\text{NP}$. In particular, the result holds for
more >>>