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$?

  • 3
    $\begingroup$ 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$? $\endgroup$
    – James King
    Commented Jun 13, 2011 at 7:54
  • $\begingroup$ Sorry, f($\Delta$) indeed. $\endgroup$
    – Regularity
    Commented Jun 13, 2011 at 13:00

2 Answers 2


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)

  • 2
    $\begingroup$ The file is damaged and could not be repaired.... $\endgroup$
    – James King
    Commented Jun 13, 2011 at 13:55
  • $\begingroup$ link does not work anymore. $\endgroup$
    – oerpli
    Commented Mar 19, 2016 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.

  • 1
    $\begingroup$ 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$. $\endgroup$ Commented Apr 21, 2015 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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