<p>As detailed below, the problem of finding an independent set of size <span class="math-container">$\Omega(n^{1-\delta})$</span> in 3-colorable graphs is essentially equivalent to <span class="math-container">$O(n^\delta)$</span>-approximating 3-COLOR.  Currently, the best poly-time approximation ratio known to be achievable for 3-COLOR is <span class="math-container">$O(n^\delta)$</span> for <span class="math-container">$\delta&gt;0.19$</span>.  If you could find independent sets of size <span class="math-container">$\Omega(n^{0.81})$</span> in 3-colorable graphs in polynomial time, you could achieve a poly-time  approximation ratio of <span class="math-container">$O(n^{0.19})$</span> for 3-COLOR, beating the best current ratio.</p>
<p>(Here, by <em><span class="math-container">$f(n)$</span>-approximating 3-COLOR</em>, I mean the following problem: <em>given a 3-colorable graph with <span class="math-container">$n$</span> vertices, find a coloring of size at most <span class="math-container">$3f(n)$</span>.</em></p>
<p><strong>Lemma 1.</strong> <em>Fix any constant <span class="math-container">$\delta&gt;0$</span>. There is a poly-time <span class="math-container">$O(n^\delta)$</span>-approximation algorithm for 3-COLOR if and only if there is a poly-time algorithm for finding an independent set of size <span class="math-container">$\Omega(n^{1-\delta})$</span> in any given 3-colorable graph.</em></p>
<p><em>Proof.</em>
The &quot;only if&quot; direction is easy. Just compute a coloring that uses at most <span class="math-container">$O(n^\delta)$</span> colors and return the largest color class.  This is necessarily an independent set of size at least <span class="math-container">$\Omega(n/n^{\delta}) = \Omega(n^{1-\delta})$</span>.</p>
<p>The &quot;if&quot; direction is not much harder.  Suppose that algorithm <span class="math-container">$A$</span> finds an independent set of size <span class="math-container">$\Omega(n^{1-\delta})$</span> in any given 3-colorable graph in polynomial time.  Given a graph <span class="math-container">$G=(V, E)$</span>, define algorithm <span class="math-container">$B$</span> to find a coloring for <span class="math-container">$G$</span> as follows: use <span class="math-container">$A$</span> to find a large independent set <span class="math-container">$S$</span> in <span class="math-container">$G$</span>, recurse on the graph <span class="math-container">$G'$</span> obtained by deleting the vertices in <span class="math-container">$S$</span> from <span class="math-container">$G$</span> to find a coloring of <span class="math-container">$G'$</span>, then add <span class="math-container">$S$</span> as a new color to this coloring to produce a coloring of <span class="math-container">$G$</span>.  (Of course the base case is when the graph has no vertices.)  Note that <span class="math-container">$G'$</span> is 3-colorable, so the algorithm is well-defined.</p>
<p>Let <span class="math-container">$C(n)$</span> be the maximum number of colors <span class="math-container">$B$</span> uses to color any 3-colorable <span class="math-container">$n$</span>-vertex graph.  Then <span class="math-container">$C(0) = 0$</span> and for <span class="math-container">$n\ge 1$</span> we have
<span class="math-container">$$C(n) \le 1 + C(\lfloor n - \Omega(n^{1-\delta})\rfloor).$$</span>
Expanding the recurrence <span class="math-container">$O((n/2)^\delta)$</span> times
until the argument has size at most <span class="math-container">$n/2$</span> we have
<span class="math-container">$$C(n) \le O((n/2)^\delta) + C(n/2).$$</span>
Expanding this in turn gives the bound
<span class="math-container">$C(n) \le O\big(\sum_{i\ge 1} (n/2^i)^\delta\big) = O(n^\delta/\delta) = O(n^\delta).~~~~~\Box$</span></p>
<p>The best poly-time approximation algorithms known for 3-COLOR <a href="https://cs.stackexchange.com/questions/144733/currently-best-approximation-for-graph-coloring">are apparently</a> <span class="math-container">$O(n^{\delta})$</span>-approximation algorithms for <span class="math-container">$\delta &gt; 0.19$</span>.  (For a good survey of these results see the introduction of <a href="https://doi.org/10.1145/3001582" rel="nofollow noreferrer">this paper</a>.)  If you could find independent sets of size <span class="math-container">$\Omega(n^{0.81})$</span> in 3-colorable graphs in polynomial time, this would directly yield an <span class="math-container">$O(n^{0.19})$</span>-approximation algorithm for 3-COLOR, better than these currently known results.</p>
<p>For graph coloring in general, Lund and Yannakakis <a href="https://doi.org/10.1145/185675.306789" rel="nofollow noreferrer">showed</a> that, unless P=NP, for some constant <span class="math-container">$\delta &gt; 0$</span>, there is no polynomial-time <span class="math-container">$O(n^\delta)$</span>-approximation algorithm for coloring. This may hold for 3-COLOR as well, but as far as I know this has not yet been shown.  A quick search turns up a couple of recent hardness results: <a href="https://doi.org/10.1137/1.9781611975994.86" rel="nofollow noreferrer">this</a> and <a href="https://scholar.google.com/scholar?hl=en&amp;as_sdt=0%2C22&amp;q=d-To-1+Hardness+of+Coloring+3-Colorable+Graphs+with+O(1)+Colors" rel="nofollow noreferrer">this</a>.</p>

CC BY-SA 4.0
2022-11-28T10:44:33.200Z
Thank you very much for answering my question and for the detailed survey. A follow-up question if I may: Would the problem remains as hard (or, at least without a known algorithm) if each vertex $v \in V$ has a degree at least $d(v) \geq \Omega(\delta \cdot n)$?
John
CC BY-SA 4.0
2022-11-28T15:17:59.937Z
Not as hard, I think.  For example, you could do something like the following.  Given a 3-colorable graph $G$, let $d$ be the maximum degree of any vertex in $G$ and let $v$ be a vertex of degree $d$.  Find a 2-coloring $C$ of the neighbor set of $v$ (this must exist and can be found in linear time).  Return the larger of the two color classes in $C$.  Then each color class in $C$ is an independent set, and the largest one has size at least $d/2$, so this linear-time algorithm returns an independent set of size at least $d/2$.  In your case this is $\Omega(\delta n)$.  Probably can do better.
Neal Young
CC BY-SA 4.0
2022-11-28T18:06:53.500Z
Thank you!, this was helpful:)
John
CC BY-SA 4.0
2022-11-26T22:39:53.090Z
2022-11-27T21:49:20.523Z
2022-11-27T21:49:20.523Z
Neal Young
<p>Let <span class="math-container">$G = (V,E)$</span> be an undirected graph such that there is a proper coloring of the vertices of <span class="math-container">$G$</span> in three colors.</p>
<p><strong>Question:</strong> In such graphs, are there known results for the hardness of finding a maximum independent set? e.g., can one find an Independent set of cardinality at least  <span class="math-container">$\varepsilon \cdot |V|$</span> in polynomial time for some constant <span class="math-container">$\varepsilon&gt;0$</span>?</p>

<graph-theory><graph-algorithms><approximation-hardness><graph-colouring><independent-set>
Hardness of Maximum Independent Set in 3-Colorable Graphs
John
# Hardness of Maximum Independent Set in 3-Colorable Graphs

(Asked by: username_0 on 2022-11-24)

Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors.

**Question:** In such graphs, are there known results for the hardness of finding a maximum independent set? e.g., can one find an Independent set of cardinality at least $\varepsilon \cdot |V|$ in polynomial time for some constant $\varepsilon>0$?

**Tags:** graph-theory, graph-algorithms, approximation-hardness, graph-colouring, independent-set


---

## 1 answers

### Answer by username_1 on 2022-11-26. Score: 3 | Accepted answer

As detailed below, the problem of finding an independent set of size $\Omega(n^{1-\delta})$ in 3-colorable graphs is essentially equivalent to $O(n^\delta)$-approximating 3-COLOR. Currently, the best poly-time approximation ratio known to be achievable for 3-COLOR is $O(n^\delta)$ for $\delta>0.19$. If you could find independent sets of size $\Omega(n^{0.81})$ in 3-colorable graphs in polynomial time, you could achieve a poly-time approximation ratio of $O(n^{0.19})$ for 3-COLOR, beating the best current ratio.

(Here, by *$f(n)$-approximating 3-COLOR*, I mean the following problem: *given a 3-colorable graph with $n$ vertices, find a coloring of size at most $3f(n)$.*

**Lemma 1.** *Fix any constant $\delta>0$. There is a poly-time $O(n^\delta)$-approximation algorithm for 3-COLOR if and only if there is a poly-time algorithm for finding an independent set of size $\Omega(n^{1-\delta})$ in any given 3-colorable graph.*

*Proof.*
The "only if" direction is easy. Just compute a coloring that uses at most $O(n^\delta)$ colors and return the largest color class. This is necessarily an independent set of size at least $\Omega(n/n^{\delta}) = \Omega(n^{1-\delta})$.

The "if" direction is not much harder. Suppose that algorithm $A$ finds an independent set of size $\Omega(n^{1-\delta})$ in any given 3-colorable graph in polynomial time. Given a graph $G=(V, E)$, define algorithm $B$ to find a coloring for $G$ as follows: use $A$ to find a large independent set $S$ in $G$, recurse on the graph $G'$ obtained by deleting the vertices in $S$ from $G$ to find a coloring of $G'$, then add $S$ as a new color to this coloring to produce a coloring of $G$. (Of course the base case is when the graph has no vertices.) Note that $G'$ is 3-colorable, so the algorithm is well-defined.

Let $C(n)$ be the maximum number of colors $B$ uses to color any 3-colorable $n$-vertex graph. Then $C(0) = 0$ and for $n\ge 1$ we have
$$C(n) \le 1 + C(\lfloor n - \Omega(n^{1-\delta})\rfloor).$$
Expanding the recurrence $O((n/2)^\delta)$ times
until the argument has size at most $n/2$ we have
$$C(n) \le O((n/2)^\delta) + C(n/2).$$
Expanding this in turn gives the bound
$C(n) \le O\big(\sum\_{i\ge 1} (n/2^i)^\delta\big) = O(n^\delta/\delta) = O(n^\delta).~~~~~\Box$

The best poly-time approximation algorithms known for 3-COLOR [are apparently](https://cs.stackexchange.com/questions/144733/currently-best-approximation-for-graph-coloring) $O(n^{\delta})$-approximation algorithms for $\delta > 0.19$. (For a good survey of these results see the introduction of [this paper](https://doi.org/10.1145/3001582).) If you could find independent sets of size $\Omega(n^{0.81})$ in 3-colorable graphs in polynomial time, this would directly yield an $O(n^{0.19})$-approximation algorithm for 3-COLOR, better than these currently known results.

For graph coloring in general, Lund and Yannakakis [showed](https://doi.org/10.1145/185675.306789) that, unless P=NP, for some constant $\delta > 0$, there is no polynomial-time $O(n^\delta)$-approximation algorithm for coloring. This may hold for 3-COLOR as well, but as far as I know this has not yet been shown. A quick search turns up a couple of recent hardness results: [this](https://doi.org/10.1137/1.9781611975994.86) and [this](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=d-To-1+Hardness+of+Coloring+3-Colorable+Graphs+with+O(1)+Colors).

> **Comments:**
> **username_0**: Thank you very much for answering my question and for the detailed survey. A follow-up question if I may: Would the problem remains as hard (or, at least without a known algorithm) if each vertex $v \in V$ has a degree at least $d(v) \geq \Omega(\delta \cdot n)$?  
> **username_1**: Not as hard, I think.  For example, you could do something like the following.  Given a 3-colorable graph $G$, let $d$ be the maximum degree of any vertex in $G$ and let $v$ be a vertex of degree $d$.  Find a 2-coloring $C$ of the neighbor set of $v$ (this must exist and can be found in linear time).  Return the larger of the two color classes in $C$.  Then each color class in $C$ is an independent set, and the largest one has size at least $d/2$, so this linear-time algorithm returns an independent set of size at least $d/2$.  In your case this is $\Omega(\delta n)$.  Probably can do better.  
> **username_0**: Thank you!, this was helpful:)  

---

