Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 11 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer
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}$.

share|cite|improve this answer
$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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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