<p>Not quite what you ask for, but here's a lower bound - a graph for which any coloring will result in an independent set colored by $\sqrt{n}$ colors:</p>

<p>Take $\sqrt{n}$ copies of $K_{\sqrt{n}}$, and connect all vertices to a single vertex $s$.</p>

<p>Obviously, every set of $\sqrt{n}$ vertices from different $K$'s is independent, and in every copy of $K_{\sqrt{n}}$ you can find at least one "new" color.</p>

<p>This lower bound can easily be improved to $\sqrt{2n}$ or so if we connect $K_1,K_2,..$ to a single vertex, but it remains only $\Omega(\sqrt{n})$ colors.</p>

CC BY-SA 3.0
2014-02-26T12:18:32.867Z
The second example does not seems to improve the bound. I think that any IS can be colored using $2\sqrt{2n}/3$. For example, for n=9, $K_1$ is colored by blue, $K_2$ by green and red, and $K_3$ by blue, green and red. Any maximal IS is colored by 2 colors, not 3.
user15669
CC BY-SA 3.0
2014-02-26T12:22:30.730Z
I'm not sure what you mean.
The second example does improve the bound, but not asymptotically. You can construct a ~$2\sqrt n$ sized colorful IS using the vertex from $K_1$, the vertex from $K_2$ with a different color, and so on (from $K_i$ we'll take a vertex colored by a color that doesn't yet exist in our IS).

And this holds for every coloring of $G$.
R B
CC BY-SA 3.0
2014-02-26T18:29:24.920Z
Also, in your example, the IS which includes the blue vertex from $K_1$, the green from $K_2$ and the red from $K_3$ is colored by 3 colors.
R B
CC BY-SA 3.0
2014-02-27T09:47:03.820Z
@RB thank you for the example. your second graph gives a lower bound roughly $t \approx \sqrt{2n}$, this is the number such that $1+2+\dots + t = n$.
Igor Shinkar
CC BY-SA 3.0
2014-02-25T14:09:55.347Z
2014-05-23T14:21:57.553Z
2014-05-23T14:21:57.553Z
R B
<p>What about the following proof? If $\alpha(G) \leq \sqrt{n}$, then the claim holds obviously. Suppose the contrary, and let $I$ be an independent set of $G$ with maximum cardinality $\alpha$. Color $I$ with color 1, and recursively color the graph $G - I$ with colors $2,...,c$. Now, if $K$ is an independent set of $G$, consider $K' = K - I$. By induction hypothesis, $K'$ is colored with at most $\sqrt{n-\alpha}$ colors, and thus $K$ is colored with at most $1+\sqrt{n-\alpha} \leq \sqrt{n}$ colors; the inequality holds by the assumption that $\alpha \geq \sqrt{n}$.</p>

CC BY-SA 3.0
2014-02-26T12:23:04.950Z
$1+\sqrt{n-\sqrt{n}}>\sqrt{n}$, but this proof can probably be modified to show that for any $\epsilon>0$ any IS is colored by at most $(1+\epsilon)\sqrt{n}+C_\epsilon$ colors. In any case, this is a reference request, not a request for proof.
user15669
CC BY-SA 3.0
2014-02-26T13:32:42.313Z
Indeed, the proof should work by replacing $\sqrt{n}$ with $2 \sqrt{n}$. I apologize for having missed the "reference request" part, but shouldn't this result be considered as folklore? BTW, I'm the same person as above but I need to find a way to consolidate my different profiles, I should probably ask for this on meta.cstheory.stackexchange.
Super0
CC BY-SA 3.0
2014-02-26T17:40:50.300Z
(on the profile merge request) meta is a good place to post such a request.
Suresh Venkat
CC BY-SA 3.0
2014-02-26T00:58:46.740Z
2014-02-26T00:58:46.740Z
Super8
<p>The following claim is known to me, but may not count because it is unpublished:
Any graph on $n$ vertices can be colored so that any induced subgraph $H$ of chromatic number at most $k$ uses at most $\chi(H)+B$ colors,
where $B(B+1)\leq 2kn$.</p>

<p>This is a proof by induction; the motivation was to consider colorings which use few colors not only on the graph but also on all induced subgraphs.
I am not aware of any published results, though.</p>

CC BY-SA 3.0
2014-02-25T20:59:53.703Z
2014-02-25T20:59:53.703Z
Aravind
<p>Is the following claim known?</p>

<p><strong>Claim</strong>: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.</p>

<reference-request><graph-colouring>
Graph coloring minimizing the number of colors in every independent set
Igor Shinkar
# Graph coloring minimizing the number of colors in every independent set

(Asked by: username_0 on 2014-02-25)

Is the following claim known?

**Claim**: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.

**Tags:** reference-request, graph-colouring


---

## 3 answers

### Answer by username_6 on 2014-02-25. Score: 11 | Accepted answer

The following claim is known to me, but may not count because it is unpublished:
Any graph on $n$ vertices can be colored so that any induced subgraph $H$ of chromatic number at most $k$ uses at most $\chi(H)+B$ colors,
where $B(B+1)\leq 2kn$.

This is a proof by induction; the motivation was to consider colorings which use few colors not only on the graph but also on all induced subgraphs.
I am not aware of any published results, though.


---

### Answer by username_1 on 2014-02-25. Score: 10

Not quite what you ask for, but here's a lower bound - a graph for which any coloring will result in an independent set colored by $\sqrt{n}$ colors:

Take $\sqrt{n}$ copies of $K\_{\sqrt{n}}$, and connect all vertices to a single vertex $s$.

Obviously, every set of $\sqrt{n}$ vertices from different $K$'s is independent, and in every copy of $K\_{\sqrt{n}}$ you can find at least one "new" color.

This lower bound can easily be improved to $\sqrt{2n}$ or so if we connect $K\_1,K\_2,..$ to a single vertex, but it remains only $\Omega(\sqrt{n})$ colors.

> **Comments:**
> **username_2**: The second example does not seems to improve the bound. I think that any IS can be colored using $2\sqrt{2n}/3$. For example, for n=9, $K_1$ is colored by blue, $K_2$ by green and red, and $K_3$ by blue, green and red. Any maximal IS is colored by 2 colors, not 3.  
> **username_1**: I'm not sure what you mean. The second example does improve the bound, but not asymptotically. You can construct a ~$2\sqrt n$ sized colorful IS using the vertex from $K_1$, the vertex from $K_2$ with a different color, and so on (from $K_i$ we'll take a vertex colored by a color that doesn't yet exist in our IS).  And this holds for every coloring of $G$.  
> **username_1**: Also, in your example, the IS which includes the blue vertex from $K_1$, the green from $K_2$ and the red from $K_3$ is colored by 3 colors.  
> **username_0**: @RB thank you for the example. your second graph gives a lower bound roughly $t \approx \sqrt{2n}$, this is the number such that $1+2+\dots + t = n$.  

---

### Answer by username_3 on 2014-02-26. Score: 5

What about the following proof? If $\alpha(G) \leq \sqrt{n}$, then the claim holds obviously. Suppose the contrary, and let $I$ be an independent set of $G$ with maximum cardinality $\alpha$. Color $I$ with color 1, and recursively color the graph $G - I$ with colors $2,...,c$. Now, if $K$ is an independent set of $G$, consider $K' = K - I$. By induction hypothesis, $K'$ is colored with at most $\sqrt{n-\alpha}$ colors, and thus $K$ is colored with at most $1+\sqrt{n-\alpha} \leq \sqrt{n}$ colors; the inequality holds by the assumption that $\alpha \geq \sqrt{n}$.

> **Comments:**
> **username_2**: $1+\sqrt{n-\sqrt{n}}>\sqrt{n}$, but this proof can probably be modified to show that for any $\epsilon>0$ any IS is colored by at most $(1+\epsilon)\sqrt{n}+C_\epsilon$ colors. In any case, this is a reference request, not a request for proof.  
> **username_4**: Indeed, the proof should work by replacing $\sqrt{n}$ with $2 \sqrt{n}$. I apologize for having missed the "reference request" part, but shouldn't this result be considered as folklore? BTW, I'm the same person as above but I need to find a way to consolidate my different profiles, I should probably ask for this on meta.cstheory.stackexchange.  
> **username_5**: (on the profile merge request) meta is a good place to post such a request.  

---

