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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ 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. $\endgroup$ Feb 26, 2014 at 12:18
-
$\begingroup$ 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$. $\endgroup$– R BFeb 26, 2014 at 12:22
-
$\begingroup$ 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. $\endgroup$– R BFeb 26, 2014 at 18:29
-
1$\begingroup$ @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$. $\endgroup$ Feb 27, 2014 at 9:47
$\begingroup$
$\endgroup$
3
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$\begingroup$ $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. $\endgroup$ Feb 26, 2014 at 12:23
-
1$\begingroup$ 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. $\endgroup$– Super0Feb 26, 2014 at 13:32
-
$\begingroup$ (on the profile merge request) meta is a good place to post such a request. $\endgroup$ Feb 26, 2014 at 17:40