Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $\chi(G)$ and $k$? Say of the form $\chi(G)\le f(\Delta)\frac{n}{k}$ for some function $f$?

• What is $d$? I'm assuming you want this function $f(d)$ to be independent of $\Delta$? If so, how can $\Delta$ help us? If not, do you want something better than the trivial bound of $\Delta+1$? – James King Jun 13 '11 at 7:54
• Sorry, f($\Delta$) indeed. – Regularity Jun 13 '11 at 13:00

Obviously if $f(\Delta)=2\Delta$ then the bound holds. However, I doubt this is what you meant. Perhaps you meant $\chi(G) \leq f(\frac n k)$, in which case the answer is no, there is no such function.

Let $\alpha$ be the size of a maximum independent set in $G$. Then it is easy to see that the fractional chromatic number satisfies the bound $\chi_f(G)\geq \frac n \alpha$. One such example is the Kneser graph $K_{kb:b}$ for fixed integers $k$ and $b$. This graph has fractional chromatic number $k = \frac n\alpha$, and chromatic number $(k-2)b+2$. So for fixed $k$ and large $b$ the answer is no.

(See Section 3.1 of my thesis for more details. http://www.columbia.edu/~ak3074/papers/phdthesis-compact.pdf)

• The file is damaged and could not be repaired.... – James King Jun 13 '11 at 13:55
• link does not work anymore. – oerpli Mar 19 '16 at 13:59

χ(G) + α(G) <= n+1 where n is the number of vertices of the graph.

Proof by Induction: Notice that a single vertex has χ(G) + α(G) = 2. Add each vertex one by one. Notice that by adding a single vertex you can only increase them by one. By doing this, we convert G into G*. Say the new vertex v is connected to vertices 1 through r of our previous G and not connected to the vertices r+1 through n. For the inequality to be disturbed according to our induction hypothesis both have to be increased at one point

For χ(G) to increase, the 1 through r vertices, v is connected to needs r colours in any proper colouring of G. Thus |r| >= χ(G). Also the maximum independent set that v must be part of has to be contained in G - r. Therefore |G - r| >= α(G) Adding the two inequalities gets you |G| = n >= χ(G) + α(G)

Now both increase, showing that n+2>=χ(G*) + α(G*) Thus χ(G*) + α(G*) <= |G*| + 1 QED The bound is tight for complete graphs and null graphs.

• I think that your statement has an obvious (non-inductive) proof. Take a maximal independent set $S$ in your graph, color all the vertices of $S$ with color 1, and all the remaining vertices of $G$ with pairwise distinct colors. You obtain a coloring of $G$ with $n-\alpha(G)+1$ colors, so $\chi(G)+\alpha(G)\leq n+1$. – Louis Esperet Apr 21 '15 at 8:02