It is known that there is no $2^{o(n)}$-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. Is a there a similar result for $k$-COLORABILITY assuming only ETH (not SETH)?

Emden-Weinert et al. [2] proved that for all $k\geq 3$, $k$-COLORABILITY is NP-complete for graphs of maximum degree $k-1+\sqrt{k}$. By an alternate reduction, I can show that there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY in graphs of maximum degree $k-1+\sqrt{k}$ (assuming ETH). I suppose this is not a new result. Could you please point me to a paper that gives this result? (I hate to brand results as folklore). Thanks in advance.

[1] Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz, Tight bounds for graph homomorphism and subgraph isomorphism, Krauthgamer, Robert (ed.), Proceedings of SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: SIAM; New York, NY: ACM. 1643-1649 (2016). ZBL1409.68209.

[2] Emden-Weinert, Thomas; Hougardy, Stefan; Kreuter, Bernd, Uniquely colourable graphs and hardness of colouring graphs of large girth, Comb. Probab. Comput. 7, No. 4, 375-386 (1998). ZBL0918.05051.

  • $\begingroup$ What is $O^*(2^{o(n)})$? $\endgroup$ Mar 25, 2021 at 11:15
  • $\begingroup$ $O^*(2^{o(n)})$ hides a polynomial factor in the size of the graph (i.e., poly($m+n$) ). $\endgroup$ Mar 25, 2021 at 11:35
  • 3
    $\begingroup$ Well, $m=O(n^2)$, and $n^{O(1)}=2^{o(n)}$, isn’t it? So then $O^*(2^{o(n)})=2^{o(n)}$. $\endgroup$ Mar 25, 2021 at 11:55
  • $\begingroup$ @EmilJeřábek Yes, you are right. In this case, $O^*$ notation is not relevant. $\endgroup$ Mar 26, 2021 at 0:44
  • $\begingroup$ "... unless ETH fails [1]. Is a there a similar result for k-COLORABILITY assuming only ETH (not SETH)?" I assumed "unless ETH fails" was a typo and that you meant "unless SETH fails," but I checked the Cygan et al. result and it looks like it really does just assume ETH, so now I don't understand the question. $\endgroup$ Mar 28, 2021 at 18:16

1 Answer 1


The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for $k$-COLORABILITY $\leq_p$ $(k+1)$-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction.
Also, the reduction $k$-COLORABILITY $\leq_p$ $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$) given by Emden-Weinert et al. [2] is a linear reduction.

From these observations, it follows that, unless ETH fails, there is no $2^{o(n)}$-time algorithm for $k$-COLORABILITY($\Delta\leq k-1+\lceil \sqrt{k} \rceil$), .

Detailed Explanation:

Let $G$ be a graph of maximum degree $4$ as constructed in the hardness result of Cygan et al [1].

Add $k-4$ new vertices to $G$ and connect them to all vertices of $G$ as well as to themselves, the resulting graph $G'$ has an unbounded degree but, all except $k-4$ of the vertices has degree at most $k$. We do not know whether $G'$ is $k$-colorable. The number of newly added edges and vertices for a constant $k$ is $O(n)$, thus any $2^{o(n)}$ algorithm for $k$-coloring of $G'$ falsifies ETH.

The second step is to reduce the maximum degree of $G'$ by the method provided in the work of Emden-Weinert et al. [2]. Their method roughly speaking is as follows: they take a high degree vertex $u$ then remove $k$ edges of $u$ and add $k-1$ new edges to $u$ to connect it to a specific gadget with $O(k)$ many vertices. This procedure clearly reduces the degree of $u$ by one, and if we repeat this process $n-k$ times, the degree of $u$ will be at most $k$. They showed that the newly created graph after this step exhibits a similar coloring scheme as the original graph (except for the gadgets). As long as there is a high degree vertex, they repeat the mentioned degree reduction procedure. Additionally, based on their construction, we know that the maximum degree of vertices inside gadgets is at most $k-1+\lceil \sqrt{k} \rceil$, thus once the procedure ends, the resulting graph has the claimed maximum degree.

Observe that we have to perform the aforementioned procedure only on $k$ vertices of $G'$ and since their degree is $n+k-4$, after at most $O(kn)$ iterations the procedure stops. Additionally in each iteration, we add at most $O(k)$ new vertices, which means by the end of the procedure, the constructed graph has at most $O(k^2n)$ vertices. Hence, any $2^{o(k^2n)}$ algorithm for $k$-coloring of this graph, would result in a $2^{o(n)}$ algorithm for $3$-coloring of the input graph $G$. Since $k$ is a fixed constant, we conclude that any $2^{o(n)}$ algorithm for k-coloring on this graph would lead us to a $2^{o(n)}$ algorithm for $3$-coloring of $G$.

  • $\begingroup$ Sorry, first I couldn't see that the reduction in Emden-Weinert et al. [2] is linear. Hence, the question. $\endgroup$ Mar 31, 2021 at 5:25
  • $\begingroup$ I think you should be a bit careful on this argument, the reduction in ref 2 may add O(mk) new vertices, thus the graph at the end can simply have m vertices, and a $2^{o(m)}$ algorithm on that graph does not imply anything on the original graph (it doesn't violate $2^{o(n)}$ lowerbound). However, since in the first step you make only one vertex of high degree, and you may repeat it at most $k$ times, it means that eventually by employing ref 2 you may add at most $O(nk)$ new vertices and now a $2^{o(nk)}$ algorithm here would falsify ETH. $\endgroup$
    – Saeed
    Mar 31, 2021 at 11:12
  • $\begingroup$ @Saeed Ref 2 argues in terms of $m$, but we can argue in terms of $n$ instead. We can replace every vertex of the initial graph $G$ by a finite garph (viz. $K_{k-1}+\lceil \sqrt{k}\rceil K_1$ plus some edges added in). So, the resultant graph has only $O(n)$ vertices (recall that $k$ is a constant). $\endgroup$ Apr 1, 2021 at 4:04
  • 1
    $\begingroup$ Also, what I wrote in the answer was just further elaboration, for example explaining the construction of the previous proof, explaining what is universal vertex and so on. Otherwise in my first comment in one line I explained why it works. Anyways, feel free to edit it, I won't suggest making it less understandable. $\endgroup$
    – Saeed
    Apr 6, 2021 at 11:15
  • 1
    $\begingroup$ Note that you are working on a new graph, not a max degree 4 graph, the new graph has vertices of degree almost $n$, but they are few (only $k$) so at the end, your argument that $m$ is linear works and I think what I wrote is the same. $\endgroup$
    – Saeed
    Apr 6, 2021 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.