# Graph coloring minimizing the number of colors in every independent set

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.

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.

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.

• 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 Feb 26 '14 at 12:18
• 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 Feb 26 '14 at 12:22
• 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 Feb 26 '14 at 18:29
• @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 Feb 27 '14 at 9:47

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

• $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 Feb 26 '14 at 12:23
• 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 Feb 26 '14 at 13:32
• (on the profile merge request) meta is a good place to post such a request. – Suresh Venkat Feb 26 '14 at 17:40