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 Jun 13 '11 at 7:54
  • $\begingroup$ Sorry, f($\Delta$) indeed. $\endgroup$ – 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)

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

  • 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$ – Louis Esperet Apr 21 '15 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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