I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it:

First question: The paper gives a proof of the following statement

Theorem 2.1: Assuming ETH, there is no $ 2^{o(klogk)}$ time algorithm for $ k \times k$ -Clique.

They prove this statement by sophisticated reduction from $ 3$ -coloring. They then state that this construction runs in time polynomial in $ k$ . They state:

The graph $ G$ has $ k^2$ vertices and the time required to construct G is polynomial in $ k$ . […] Therefore, the total running time is $ 2^{o(k \log(k)} \cdot k^{O(1)}$

Why is this not $ 2^{o(k \log(k)}) + k^{O(1)}$ instead? As far as I can see, we have only have to construct the graph once, and then we can run the presumed $ 2^{o(k \log(k)}$ algorithm.

Second question: From this theorem, it follows that $ k \times k$ -Clique can not have a $ k^{o(k)}$ algorithm under the Exponential Time Hypothesis. This follows from the abstract, which states that $ k^{O(k)} = 2^{O(k \log(k))}$ . What is a good way to proof this statement?