<p>The result mentioned in the question can be obtained by a chain of two standard reductions. The simplest reduction for <span class="math-container">$k$</span>-COLORABILITY <span class="math-container">$\leq_p$</span> <span class="math-container">$(k+1)$</span>-COLORABILITY (namely, adding a universal vertex) is clearly a linear reduction.<br />
Also, the reduction <span class="math-container">$k$</span>-COLORABILITY <span class="math-container">$\leq_p$</span> <span class="math-container">$k$</span>-COLORABILITY(<span class="math-container">$\Delta\leq k-1+\lceil \sqrt{k} \rceil$</span>) given by Emden-Weinert et al. [2] is a linear reduction.</p>
<p>From these observations, it follows that, unless ETH fails, there is no <span class="math-container">$2^{o(n)}$</span>-time algorithm for <span class="math-container">$k$</span>-COLORABILITY(<span class="math-container">$\Delta\leq k-1+\lceil \sqrt{k} \rceil$</span>), .</p>
<p><strong>Detailed Explanation:</strong></p>
<p>Let <span class="math-container">$G$</span> be a graph of maximum degree <span class="math-container">$4$</span> as constructed in the hardness result of Cygan et al [1].</p>
<p>Add <span class="math-container">$k-4$</span> new vertices to <span class="math-container">$G$</span> and connect them to all vertices of <span class="math-container">$G$</span> as well as to themselves, the resulting graph <span class="math-container">$G'$</span> has an unbounded degree but, all except <span class="math-container">$k-4$</span> of the vertices has degree at most <span class="math-container">$k$</span>. We do not know whether <span class="math-container">$G'$</span> is <span class="math-container">$k$</span>-colorable. The number of newly added edges and vertices for a constant <span class="math-container">$k$</span> is <span class="math-container">$O(n)$</span>, thus any <span class="math-container">$2^{o(n)}$</span> algorithm for <span class="math-container">$k$</span>-coloring of <span class="math-container">$G'$</span> falsifies ETH.</p>
<p>The second step is to reduce the maximum degree of <span class="math-container">$G'$</span> 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 <span class="math-container">$u$</span> then remove <span class="math-container">$k$</span> edges of <span class="math-container">$u$</span> and add <span class="math-container">$k-1$</span> new edges to <span class="math-container">$u$</span> to connect it to a specific gadget with <span class="math-container">$O(k)$</span> many vertices. This procedure clearly reduces the degree of <span class="math-container">$u$</span> by one, and if we repeat this process <span class="math-container">$n-k$</span> times, the degree of <span class="math-container">$u$</span> will be at most <span class="math-container">$k$</span>. 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 <span class="math-container">$k-1+\lceil \sqrt{k} \rceil$</span>, thus once the procedure ends, the resulting graph has the claimed maximum degree.</p>
<p>Observe that we have to perform the aforementioned procedure only on <span class="math-container">$k$</span> vertices of <span class="math-container">$G'$</span> and since their degree is <span class="math-container">$n+k-4$</span>, after at most <span class="math-container">$O(kn)$</span> iterations the procedure stops. Additionally in each iteration, we add at most <span class="math-container">$O(k)$</span> new vertices, which means by the end of the procedure, the constructed graph has at most <span class="math-container">$O(k^2n)$</span> vertices. Hence, any <span class="math-container">$2^{o(k^2n)}$</span> algorithm for <span class="math-container">$k$</span>-coloring of this graph, would result in a <span class="math-container">$2^{o(n)}$</span> algorithm for <span class="math-container">$3$</span>-coloring of the input graph <span class="math-container">$G$</span>. Since <span class="math-container">$k$</span> is a fixed constant, we conclude that any <span class="math-container">$2^{o(n)}$</span> algorithm for k-coloring on this graph would lead us to a <span class="math-container">$2^{o(n)}$</span> algorithm for <span class="math-container">$3$</span>-coloring of <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2021-03-31T05:25:28.317Z
Sorry, first I couldn't see that the reduction in Emden-Weinert et al. [2] is linear. Hence, the question.
Cyriac Antony
CC BY-SA 4.0
2021-03-31T11:12:08.520Z
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.
Saeed
CC BY-SA 4.0
2021-04-01T04:04:28.537Z
@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).
Cyriac Antony
CC BY-SA 4.0
2021-04-01T08:17:44.953Z
What do you mean we can argue w.r.t. n? Maybe you didn’t understand the proof of ref 2, what is K1 in your argument, do you have a new proof in mind? They don’t replace a vertex with anything. They add a gadget of size O(k) to a vertex of high degree, in return reduces the degree of that vertex by 1. This is why they may have O(mk) vertices, since they may need to remove O(m) edges. However, as I said in the previous comment, for your case, you don’t need a new proof, since after adding k new vertices to your graph, you need to remove O(kn) edges, it means you add at most $O(nk^2)$ vertices.
Saeed
CC BY-SA 4.0
2021-04-05T04:18:26.400Z
@Saeed Okay, I misunderstood the construction. Now, I am not sure whether the reduction given in [2] is linear. Please feel free to edit the answer (it is community-wiki).
Cyriac Antony
CC BY-SA 4.0
2021-04-06T10:49:39.607Z
I've added some explanation, hopefully, it is clear now. The reduction in 2 is quadratic for general graphs, but for this specific purpose, it will be implemented with linear modifications.
Saeed
CC BY-SA 4.0
2021-04-06T11:14:05.107Z
Adding universal vertices makes $\Delta$ big, also please use $n$ for the number of vertices and $m$ for the number of edges.
Saeed
CC BY-SA 4.0
2021-04-06T11:15:32.693Z
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.
Saeed
CC BY-SA 4.0
2021-04-06T11:18:28.930Z
I think I have a shorter proof now. The graph $′$ constructed in Emden-Weinert et al. [2] has $(+)$ vertices where $m=|()|$ and $n=|()|$. Since $\leq \Delta()/2$ and $\Delta()\leq 4$, $(+)=()$ (for graphs of max. degree 4). So, $′$ has $()$ vertices.
Cyriac Antony
CC BY-SA 4.0
2021-04-06T11:27:38.960Z
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.
Saeed
CC BY-SA 4.0
2021-03-31T05:23:42.140Z
2021-04-06T10:46:48.783Z
2021-04-06T10:46:48.783Z
Cyriac Antony
<p>It is known that there is no <span class="math-container">$2^{o(n)}$</span>-time algorithm for 3-COLORABILITY of graphs of maximum degree four, unless ETH fails [1]. <strong>Is a there a similar result for <span class="math-container">$k$</span>-COLORABILITY assuming only ETH</strong> (not SETH)?</p>
<p>Emden-Weinert et al. [2] proved that for all <span class="math-container">$k\geq 3$</span>, <span class="math-container">$k$</span>-COLORABILITY is NP-complete for graphs of maximum degree <span class="math-container">$k-1+\sqrt{k}$</span>. By an alternate reduction, I can show that there is no <span class="math-container">$2^{o(n)}$</span>-time algorithm for <span class="math-container">$k$</span>-COLORABILITY in graphs of maximum degree <span class="math-container">$k-1+\sqrt{k}$</span> (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.</p>
<p><strong>References</strong><br />
[1] <em>Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socała, Arkadiusz</em>, <a href="http://dx.doi.org/10.1137/1.9781611974331.ch112" rel="nofollow noreferrer"><strong>Tight bounds for graph homomorphism and subgraph isomorphism</strong></a>, Krauthgamer, Robert (ed.), Proceedings of SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: SIAM; New York, NY: ACM. 1643-1649 (2016). <a href="https://zbmath.org/?q=an:1409.68209" rel="nofollow noreferrer">ZBL1409.68209</a>.</p>
<p>[2] <em>Emden-Weinert, Thomas; Hougardy, Stefan; Kreuter, Bernd</em>, <a href="http://dx.doi.org/10.1017/S0963548398003678" rel="nofollow noreferrer"><strong>Uniquely colourable graphs and hardness of colouring graphs of large girth</strong></a>, Comb. Probab. Comput. 7, No. 4, 375-386 (1998). <a href="https://zbmath.org/?q=an:0918.05051" rel="nofollow noreferrer">ZBL0918.05051</a>.</p>

CC BY-SA 4.0
2021-03-25T11:15:14.583Z
What is $O^*(2^{o(n)})$?
Emil Jeřábek
CC BY-SA 4.0
2021-03-25T11:35:34.167Z
$O^*(2^{o(n)})$ hides a polynomial factor in the size of the graph (i.e., poly($m+n$) ).
Cyriac Antony
CC BY-SA 4.0
2021-03-25T11:55:58.337Z
Well, $m=O(n^2)$, and $n^{O(1)}=2^{o(n)}$, isn’t it? So then $O^*(2^{o(n)})=2^{o(n)}$.
Emil Jeřábek
CC BY-SA 4.0
2021-03-26T00:44:42.773Z
@EmilJeřábek Yes, you are right. In this case, $O^*$ notation is not relevant.
Cyriac Antony
CC BY-SA 4.0
2021-03-28T18:16:43.957Z
"... 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.
Huck Bennett
CC BY-SA 4.0
2021-03-29T04:09:00.747Z
@HuckBennett, I don't see the result in Cygan et al. Could you please give the theorem number in the book. Note that I talking about k-COLORABILITY of graphs of maximum degree $k-1+\sqrt{k}$. Does Cygan et al.'s result you mention work directly for this degree bound?
Cyriac Antony
<lower-bounds><graph-colouring><complexity-assumptions>
ETH based lower bound for $k$-COLORING of bounded degree graph
Cyriac Antony
# ETH based lower bound for $k$-COLORING of bounded degree graph

(Asked by: username_0 on 2021-03-25)

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.

**References**  
[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**](http://dx.doi.org/10.1137/1.9781611974331.ch112), 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](https://zbmath.org/?q=an:1409.68209).

[2] *Emden-Weinert, Thomas; Hougardy, Stefan; Kreuter, Bernd*, [**Uniquely colourable graphs and hardness of colouring graphs of large girth**](http://dx.doi.org/10.1017/S0963548398003678), Comb. Probab. Comput. 7, No. 4, 375-386 (1998). [ZBL0918.05051](https://zbmath.org/?q=an:0918.05051).

**Tags:** lower-bounds, graph-colouring, complexity-assumptions
> **Comments:**
> **username_1**: What is $O^*(2^{o(n)})$?  
> **username_0**: $O^*(2^{o(n)})$ hides a polynomial factor in the size of the graph (i.e., poly($m+n$) ).  
> **username_1**: Well, $m=O(n^2)$, and $n^{O(1)}=2^{o(n)}$, isn’t it? So then $O^*(2^{o(n)})=2^{o(n)}$.  
> **username_0**: @EmilJeřábek Yes, you are right. In this case, $O^*$ notation is not relevant.  
> **username_2**: "... 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.  
> **username_0**: @HuckBennett, I don't see the result in Cygan et al. Could you please give the theorem number in the book. Note that I talking about k-COLORABILITY of graphs of maximum degree $k-1+\sqrt{k}$. Does Cygan et al.'s result you mention work directly for this degree bound?  

---

## 1 answers

### Answer by username_0 on 2021-03-31. Score: 1 | Accepted answer

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$.

> **Comments:**
> **username_0**: Sorry, first I couldn't see that the reduction in Emden-Weinert et al. [2] is linear. Hence, the question.  
> **username_3**: 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.  
> **username_0**: @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).  
> **username_3**: What do you mean we can argue w.r.t. n? Maybe you didn’t understand the proof of ref 2, what is K1 in your argument, do you have a new proof in mind? They don’t replace a vertex with anything. They add a gadget of size O(k) to a vertex of high degree, in return reduces the degree of that vertex by 1. This is why they may have O(mk) vertices, since they may need to remove O(m) edges. However, as I said in the previous comment, for your case, you don’t need a new proof, since after adding k new vertices to your graph, you need to remove O(kn) edges, it means you add at most $O(nk^2)$ vertices.  
> **username_0**: @Saeed Okay, I misunderstood the construction. Now, I am not sure whether the reduction given in [2] is linear. Please feel free to edit the answer (it is community-wiki).  
> **username_3**: I've added some explanation, hopefully, it is clear now. The reduction in 2 is quadratic for general graphs, but for this specific purpose, it will be implemented with linear modifications.  
> **username_3**: Adding universal vertices makes $\Delta$ big, also please use $n$ for the number of vertices and $m$ for the number of edges.  
> **username_3**: 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.  
> **username_0**: I think I have a shorter proof now. The graph $′$ constructed in Emden-Weinert et al. [2] has $(+)$ vertices where $m=|()|$ and $n=|()|$. Since $\leq \Delta()/2$ and $\Delta()\leq 4$, $(+)=()$ (for graphs of max. degree 4). So, $′$ has $()$ vertices.  
> **username_3**: 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.  

---

